Given a context-free grammar (GLC) G, transforms it into an equivalent GLC G' in Chomsky normal form.
GLC G: (V,Σ,R,P), ∀R: (X → w) ∧ (X ∈ V) ∧ (w ∈ (V ∪ Σ)^*)
in short: the production(w) of every rule(R) might be any combination of the language's alphabet(Σ) and variables(V).
GLC in CNF G': (V, Σ, R, P), if λ ∈ L(G') then P → λ, ∀R: (X → YZ for X, Y, Z ∈ V) ∨ (X → a for a ∈ Σ)
in short: the initial variable(P) generates lambda(λ) if its contained by the language, and all of the other rules must either product exactly two more rules(YZ) concatenated or a simbol(a) of the alphabet(Σ).
There are several manipulations of a GLC which doesn't alter the generated language, although restructures the grammar rules productions. When applying multiple types of deletions in sequence, some rule types that have already been deleted may reappear, in order to avoid it there is a carefully defined sequence procedure to preserve elimination consistency(before and after):
python3 chomsky.py G.json
Try to convert a CFG to Greibach's Normal Form(GNF)!
GLC in GNF G'' = (V, Σ, R, P), if λ ∈ L(G'') then P → λ, ∀R: X → ay for a ∈ Σ and y ∈ V^*
in short: the initial variable(P) generates lambda(λ) if its contained by the language, and all of the other rules must product exactly one simbol(a) of the alphabet(Σ) followed by any combination of other rules(y) concatenated.
How to? Have a peek of the methods:
- Elimination of left recursive rules.
- Variable in Rule elimination.
-
Hopcroft J., Motwani R. Ullman J.; Introduction to Automata Theory, Languages, and Computation; 3rd edition, 2006.
-
Vieira N.; Introdução aos Fundamentos da Computação; 1a edição, 2006.