Simplification of CFG; CNF, GNF & BNF
Open in the Padhaiko appSimplification of CFG; CNF, GNF and BNF
Context-free grammars written directly from linguistic intuition often contain redundant, non-terminating, or empty transitions. To facilitate efficient syntactic parsing, membership testing (such as the CYK algorithm), and formal equivalence proofs, grammars undergo systematic simplification and can be transformed into standardized normal forms—primarily Chomsky Normal Form (CNF), Greibach Normal Form (GNF), and Backus-Naur Form (BNF).
3.3 Simplification of Context-Free Grammars
A grammar is said to be simplified when it is stripped of all redundant symbols and rules that do not contribute to generating strings in the language. Simplification consists of three modular operations performed in sequence:
- Elimination of Useless Symbols (non-generating and unreachable symbols).
- Elimination of -Productions (null productions).
- Elimination of Unit Productions (productions of the form ).
Useless Symbols and Simplification Criteria
Let be a context-free grammar:
- Generating Symbol: A variable is generating if there exists a derivation for some terminal string . Any variable that cannot derive a terminal string is non-generating (unyielding).
- Reachable Symbol: A symbol is reachable if there exists a derivation from the start symbol for some . Any symbol that cannot appear in a sentential form rooted at is unreachable.
- Useless Symbol: A symbol is useless if it is either non-generating or unreachable. To safely eliminate useless symbols, non-generating symbols must be eliminated first, followed by eliminating unreachable symbols.
Worked Out Examples: Simplification of CFGs
1
Eliminate unreachable symbols from the following grammar:
Beginning at start symbol :
- The right-hand side of references variables .
- Variable produces , produces , and produces .
- Variable never appears on the right-hand side of any production reachable from .
Because cannot be reached in any derivation starting from , the productions are redundant.
The simplified grammar without unreachable symbols is:
2
Simplify the following grammar by eliminating unreachable variables:
Starting from :
- The only production for is , making variable reachable.
- Variable derives terminals and introduces no new variables.
- Variable is never referenced on the right-hand side of any rule originating from .
Eliminating the unreachable variable and its rules leaves only and .
The simplified grammar is:
3
Identify and eliminate unyielding (non-generating) and unreachable productions from the following grammar:
- Terminal rule is generating.
- Terminal rule is generating.
- Variable has rules . Every production body contains ; hence cannot terminate into terminals. is non-generating.
Removing all productions containing variable :
Tracing reachability from :
- reaches .
- : because was never defined in the original grammar, production is dropped.
- Variable is now unreachable from .
The final simplified grammar is:
4
Eliminate -productions from the grammar:
A variable is nullable if it can derive . Here, , so is nullable.
In every production where appears, we form alternative rules simulating both presence and absence of :
- In :
- Keeping :
- Omitting :
- Result:
- In :
- Keeping both:
- Omitting first :
- Omitting second :
- Omitting both 's:
- Result:
The grammar free of -productions is:
5
Eliminate unit productions from the following grammar:
The unit productions are , , and . Following the transitive chain:
Thus, variable directly inherits the non-unit production .
Replacing with gives:
Variables are no longer referenced by or . Eliminating these unreachable variables finalizes the simplification.
The resulting grammar free of unit productions is:
3.4 Chomsky Normal Form (CNF)
Chomsky Normal Form (CNF)
A context-free grammar is in Chomsky Normal Form if every production rule has one of the two forms:
- (where , exactly two non-terminals).
- (where and , exactly one terminal).
If , the rule is permitted provided is the start symbol and does not appear on the right-hand side of any production.
Standard Algorithm to Convert CFG into CNF:
- New Start Symbol: If start symbol appears on the RHS or derives , introduce a new start symbol .
- Eliminate -Productions: Identify all nullable variables and generate rules without (except ).
- Eliminate Unit Productions: Remove all rules of the form .
- Eliminate Useless Symbols: Remove non-generating symbols followed by unreachable symbols.
- Isolate Terminals: For any production containing terminals alongside other symbols (length ), replace each terminal with a new variable .
- Binarize Long Productions: For any production body with three or more variables (), replace with a cascade: .
6
Convert the following context-free grammar into Chomsky Normal Form:
Variable is nullable (). Expanding nullable occurrences:
The unit rule is . Replacing with non-unit bodies of :
Introducing variables and :
The rules and have length 3:
- Introduce
- Introduce
The grammar in Chomsky Normal Form is:
3.5 Greibach Normal Form (GNF)
Greibach Normal Form (GNF)
A context-free grammar is in Greibach Normal Form if every production rule has the form:
where is a non-terminal, is exactly one terminal symbol, and is a string of zero or more non-terminals.
GNF is significant because every step in a derivation consumes exactly one input token, ensuring that derivations terminate in exactly steps.
7
Convert the following CFG into Greibach Normal Form:
Productions for and already begin with terminals:
- (all begin with terminals)
- (all begin with terminals)
- (in GNF)
In , substitute :
In , substitute :
In the rules above, and contain terminal in non-leading positions. Introducing :
The grammar in Greibach Normal Form is:
8
Convert the following CFG into GNF:
In , the variable appears in the leading position. Substituting all production bodies of :
- (each begins with a terminal followed by non-terminals)
- (in GNF)
- (in GNF)
The grammar in Greibach Normal Form is:
3.6 Backus-Naur Form (BNF)
Backus-Naur Form (BNF)
Backus-Naur Form (BNF) is a formal metasyntax notation used to describe context-free syntax:
- Non-terminal variables are enclosed in angle brackets: .
- Production assignment is denoted by the symbol .
- Alternatives are separated by vertical bars: .
- Terminal characters represent literal source tokens.
9
Define the BNF grammar for signed and unsigned decimal integers, and derive the string .
The integer is derived through signed integer expansion followed by recursive digit concatenation.
Solutions to Examination Questions: CNF Conversions
10
Convert the following CFG into CNF:
[2081 Chaitra, 2073 Chaitra]
Both and are nullable:
- In : derives .
- Because , introduce new start symbol :
- is now unreachable and eliminated.
Introduce and :
Introduce and :
The resulting CNF grammar is:
11
Convert the given CFG into CNF:
[2081 Bhadra]
is nullable:
Introduce :
Introduce and :
The CNF grammar is as specified above.
12
Convert the following CFG into CNF:
[2076 Ashwin]
Both and are nullable, leading to :
- Add new start symbol
Eliminate and , and eliminate :
Introduce :
Introduce and :
The resulting CNF grammar is established.
13
Convert the following CFG into CNF with full explanation:
[2075 Chaitra]
Because , introduce new start symbol :
Introduce :
Introduce and :
The CNF grammar is as given above.
14
Convert the following CFG into CNF with explanation:
[2075 Ashwin]
Variable is nullable ():
Replace with the non-unit productions of :
Introduce :
Introduce and :
The CNF conversion is complete.
15
Convert the following CFG into CNF with full explanation:
[2074 Ashwin]
Introduce . Eliminate -productions from and :
Eliminate unit rules , , and :
Introduce :
- Replace with and with .
Introduce :
- Replace with and with .
The grammar in CNF is:
16
Convert the following CFG into Chomsky Normal Form:
[2074 Chaitra]
Eliminate :
Eliminate unit rule :
Introduce :
Introduce :
The grammar is in Chomsky Normal Form.
17
Convert the given CFG into CNF:
[2073 Shrawan]
The variable only has the production , meaning it never derives a terminal string. is non-generating. Eliminating removes all rules referencing :
Introduce :
The resulting CNF grammar is:
Exercise Set: CFG Simplification, CNF & GNF
Exercise Questions: Simplification, CNF & GNF
Define Greibach Normal Form (GNF). [2082 Kartik]
Formal Definition of Greibach Normal Form: A context-free grammar without -productions is in Greibach Normal Form (GNF) if every production rule in is of the form:
where:
- is a single non-terminal variable.
- is exactly one terminal symbol.
- is a string of zero or more non-terminal variables ( contains no terminals).
(If the language contains , the rule is permitted provided start symbol does not appear on the right-hand side of any production.)
Key Properties and Advantages of GNF:
- Single Terminal Prefix: Every production step generates exactly one terminal symbol at the leftmost position of the sentential form ().
- Deterministic Step Count: To derive a terminal string of length , any derivation must take exactly steps. This prevents infinite derivation loops and guarantees linear-time derivations.
- Equivalence with Pushdown Automata: GNF yields a direct, one-to-one translation to a single-state Pushdown Automaton (PDA) accepting by empty stack. A production corresponds directly to the transition .
Conversion Methodology and Example: Converting an arbitrary CFG to GNF follows four stages:
- Eliminate -productions, unit productions, and useless symbols.
- Order variables as such that if , then .
- Eliminate immediate left recursion () by introducing a new variable .
- Substitute terminal-prefixed productions back into earlier rules.
Example Grammar in GNF:
Every production starts with exactly one terminal ( or ) followed exclusively by variables (), satisfying GNF.
A context-free grammar is in Greibach Normal Form (GNF) if every production rule is of the form , where is a non-terminal variable, is exactly one terminal symbol, and is a string of zero or more non-terminals (). Every derivation of a string of length requires exactly derivation steps.
How is simplification of a Context-Free Grammar performed? [2081 Bhadra]
Three-Phase Architecture and Required Order: Simplifying a CFG eliminates redundancies, non-productive cycles, and empty transitions without altering the language generated (). To guarantee that earlier transformations do not reintroduce eliminated structures, the operations must be executed in strict sequence:
- Elimination of -productions (null productions).
- Elimination of unit productions (rules of the form ).
- Elimination of useless symbols (non-generating first, then unreachable).
Eliminating Null and Unit Productions:
- Elimination of -productions ():
- Identify all nullable variables: .
- For every production , generate all variant rules by replacing subsets of nullable with .
- Delete all productions (adding only if ).
- Elimination of Unit Productions ( where ):
- For each variable , determine its unit closure: the set of all variables such that via unit rules.
- For every pair in the unit closure and each non-unit rule (), add .
- Delete all original unit rules .
Elimination of Useless Symbols: A symbol is useful if there exists a derivation for some terminal string . It requires two sub-phases:
- Generating Symbols (Phase 1):
- Base: Every terminal symbol is generating. Any variable with () is generating.
- Induction: If and every symbol in is generating, then is generating.
- Eliminate all non-generating variables and all productions containing them.
- Reachable Symbols (Phase 2):
- Base: The start symbol is reachable.
- Induction: If variable is reachable and , then every symbol appearing in is reachable.
- Eliminate all unreachable variables, terminals, and their associated productions.
Simplification of a CFG is performed in three distinct phases:
- Elimination of -productions: nullable variables are determined and productions are expanded without .
- Elimination of unit productions: transitive unit chains are resolved by replacing unit rules with the non-unit production bodies of .
- Elimination of useless symbols: non-generating symbols are eliminated first, followed by unreachable symbols.