Context-free and regular languages #
Over a finite alphabet, every regular language is context-free: the right-linear grammar
M.toContextFreeGrammar of a finite automaton M generates the language of M. The intersection
of a context-free language with a regular language is context-free. The grammar G.inter M is the
triple construction: its nonterminals are the nonterminals of G annotated with an entry and an
exit state of M, and a rule of G yields one rule for every way of threading the states of M
through its right-hand side. A fresh start symbol rewrites to the start nonterminal of G between
the start state and each accepting state of M.
Main definitions #
DFA.toContextFreeGrammar: the right-linear grammar of a finite automaton over a finite alphabet.ContextFreeGrammar.Annotates:Annotates M p l out qsays that the sentential formlisoutwith its nonterminals annotated so that the states ofMthread fromptoq.ContextFreeGrammar.inter: the grammar of the intersection of a grammar with a finite automaton.
Main results #
DFA.language_toContextFreeGrammar: the right-linear grammar ofMgenerates the language ofM, so over a finite alphabet regular languages are context-free (Language.IsRegular.isContextFree).ContextFreeGrammar.language_inter:G.inter Mgenerates the intersection.Language.IsContextFree.inf_isRegular: closure under intersection with a regular language.
Implementation notes #
The right-linear grammar of M has a nonterminal for each state, a rule q → a q' for each
transition from q to q' on the letter a, and a rule q → ε for each accepting state q;
its sentential forms are a word w followed by the state M.eval w, or an accepted word. The
alphabet must be finite, because a grammar has finitely many rules and so uses finitely many
letters: over an infinite alphabet the language of all words is regular, by a one-state
automaton, but not context-free.
References #
The right-linear grammar of M has a nonterminal for each state, a rule q → a (M.step q a)
for each state q and letter a, and a rule q → ε for each accepting state q.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The grammar of M generates the language of M.
Annotates M p l out q says that the sentential form l is out with every nonterminal
A replaced by some some (p', A, q') so that the states thread from p to q. A terminal
advances the automaton, and an annotated nonterminal jumps from its entry state to its exit
state.
- nil {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} (p : σ) : Annotates M p [] [] p
- terminal {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} {p q : σ} (a : T) {l : List (Symbol T (Option (σ × N × σ)))} {out : List (Symbol T N)} (h : Annotates M (M.step p a) l out q) : Annotates M p (Symbol.terminal a :: l) (Symbol.terminal a :: out) q
- nonterminal {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} {p p' q : σ} (A : N) {l : List (Symbol T (Option (σ × N × σ)))} {out : List (Symbol T N)} (h : Annotates M p' l out q) : Annotates M p (Symbol.nonterminal (some (p, A, p')) :: l) (Symbol.nonterminal A :: out) q
Instances For
An annotation that is a concatenation annotates a concatenation.
The annotations of out from state p, each with its exit state.
Equations
- One or more equations did not get rendered due to their size.
- ContextFreeGrammar.annotations M x✝ [] = {(x✝, [])}
Instances For
The grammar G.inter M generates the intersection of G with a finite automaton M. Its
nonterminals are those of G annotated with entry and exit states, it has each rule of G in
every annotation of its right-hand side, and its fresh start symbol none rewrites to the start
nonterminal of G between the start state and each accepting state.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The grammar generates the intersection #
Over a finite alphabet, every regular language is context-free.
Context-free languages are closed under intersection with regular languages.