PadhaikoAll subjects

Simplification of CFG; CNF, GNF & BNF

Theory of Computation (ENCT 203)

Open in the Padhaiko app

Simplification 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:

  1. Elimination of Useless Symbols (non-generating and unreachable symbols).
  2. Elimination of -Productions (null productions).
  3. Elimination of Unit Productions (productions of the form ).
Definition

Useless Symbols and Simplification Criteria

Let be a context-free grammar:

  1. 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).
  2. 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.
  3. 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

Example 1

1

Eliminate unreachable symbols from the following grammar:

Reachability Analysis from Start Symbol S

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 .
Eliminating Unreachable Productions

Because cannot be reached in any derivation starting from , the productions are redundant.

Answer:

The simplified grammar without unreachable symbols is:

Example 2

2

Simplify the following grammar by eliminating unreachable variables:

Identifying Reachable 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 Redundant Rules

Eliminating the unreachable variable and its rules leaves only and .

Answer:

The simplified grammar is:

Example 3

3

Identify and eliminate unyielding (non-generating) and unreachable productions from the following grammar:

Determining Generating Variables
  1. Terminal rule is generating.
  2. Terminal rule is generating.
  3. Variable has rules . Every production body contains ; hence cannot terminate into terminals. is non-generating.
Purging Non-Generating Variable B

Removing all productions containing variable :

Eliminating Unreachable Symbols

Tracing reachability from :

  • reaches .
  • : because was never defined in the original grammar, production is dropped.
  • Variable is now unreachable from .
Answer:

The final simplified grammar is:

Example 4

4

Eliminate -productions from the grammar:

Identifying Nullable Variables

A variable is nullable if it can derive . Here, , so is nullable.

Forming Combinations for Nullable A

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:
Answer:

The grammar free of -productions is:

Example 5

5

Eliminate unit productions from the following grammar:

Identifying Unit Production Chains

The unit productions are , , and . Following the transitive chain:

Thus, variable directly inherits the non-unit production .

Replacing Unit Rules

Replacing with gives:

Removing Unreachable Variables

Variables are no longer referenced by or . Eliminating these unreachable variables finalizes the simplification.

Answer:

The resulting grammar free of unit productions is:


3.4 Chomsky Normal Form (CNF)

Definition

Chomsky Normal Form (CNF)

A context-free grammar is in Chomsky Normal Form if every production rule has one of the two forms:

  1. (where , exactly two non-terminals).
  2. (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:

  1. New Start Symbol: If start symbol appears on the RHS or derives , introduce a new start symbol .
  2. Eliminate -Productions: Identify all nullable variables and generate rules without (except ).
  3. Eliminate Unit Productions: Remove all rules of the form .
  4. Eliminate Useless Symbols: Remove non-generating symbols followed by unreachable symbols.
  5. Isolate Terminals: For any production containing terminals alongside other symbols (length ), replace each terminal with a new variable .
  6. Binarize Long Productions: For any production body with three or more variables (), replace with a cascade: .
Example 6

6

Convert the following context-free grammar into Chomsky Normal Form:

Eliminating Null Productions

Variable is nullable (). Expanding nullable occurrences:

Eliminating Unit Productions

The unit rule is . Replacing with non-unit bodies of :

Isolating Terminals

Introducing variables and :

Binarizing Length-3 Productions

The rules and have length 3:

  • Introduce
  • Introduce
Answer:

The grammar in Chomsky Normal Form is:


3.5 Greibach Normal Form (GNF)

Definition

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.

Example 7

7

Convert the following CFG into Greibach Normal Form:

Substituting for Leading Non-Terminals in S

Productions for and already begin with terminals:

  • (all begin with terminals)
  • (all begin with terminals)
  • (in GNF)

In , substitute :

In , substitute :

Isolating Intermediate Terminals

In the rules above, and contain terminal in non-leading positions. Introducing :

Answer:

The grammar in Greibach Normal Form is:

Example 8

8

Convert the following CFG into GNF:

Substitution Analysis

In , the variable appears in the leading position. Substituting all production bodies of :

Verifying Normal Form
  • (each begins with a terminal followed by non-terminals)
  • (in GNF)
  • (in GNF)
Answer:

The grammar in Greibach Normal Form is:


3.6 Backus-Naur Form (BNF)

Definition

Backus-Naur Form (BNF)

Backus-Naur Form (BNF) is a formal metasyntax notation used to describe context-free syntax:

Example 9

9

Define the BNF grammar for signed and unsigned decimal integers, and derive the string .

BNF Grammar Specification
Deriving -108
Answer:

The integer is derived through signed integer expansion followed by recursive digit concatenation.


Solutions to Examination Questions: CNF Conversions

Example 10

10

Convert the following CFG into CNF:

[2081 Chaitra, 2073 Chaitra]

Eliminating Null Productions

Both and are nullable:

  • In : derives .
  • Because , introduce new start symbol :
Eliminating Unit Productions
  • is now unreachable and eliminated.
Isolating Terminals and Binarizing

Introduce and :

Introduce and :

Answer:

The resulting CNF grammar is:

Example 11

11

Convert the given CFG into CNF:

[2081 Bhadra]

Eliminating Null Productions

is nullable:

Eliminating Unit Production S → B
Isolating Terminals and Binarizing

Introduce :

Introduce and :

Answer:

The CNF grammar is as specified above.

Example 12

12

Convert the following CFG into CNF:

[2076 Ashwin]

Eliminating Null Productions

Both and are nullable, leading to :

  • Add new start symbol
Eliminating Unit Productions

Eliminate and , and eliminate :

Isolating Terminals and Binarizing

Introduce :

Introduce and :

Answer:

The resulting CNF grammar is established.

Example 13

13

Convert the following CFG into CNF with full explanation:

[2075 Chaitra]

Handling Null Start Symbol

Because , introduce new start symbol :

Eliminating Unit Production S' → S
Isolating Terminals and Binarizing

Introduce :

Introduce and :

Answer:

The CNF grammar is as given above.

Example 14

14

Convert the following CFG into CNF with explanation:

[2075 Ashwin]

Eliminating Null Productions

Variable is nullable ():

Eliminating Unit Production X → Y

Replace with the non-unit productions of :

Isolating Terminals and Binarizing

Introduce :

Introduce and :

Answer:

The CNF conversion is complete.

Example 15

15

Convert the following CFG into CNF with full explanation:

[2074 Ashwin]

New Start Symbol and Null Elimination

Introduce . Eliminate -productions from and :

Eliminating Unit Productions

Eliminate unit rules , , and :

Isolating Terminals and Binarizing

Introduce :

  • Replace with and with .

Introduce :

  • Replace with and with .
Answer:

The grammar in CNF is:

Example 16

16

Convert the following CFG into Chomsky Normal Form:

[2074 Chaitra]

Eliminating Null and Unit Productions

Eliminate :

Eliminate unit rule :

Isolating Terminals and Binarizing

Introduce :

Introduce :

Answer:

The grammar is in Chomsky Normal Form.

Example 17

17

Convert the given CFG into CNF:

[2073 Shrawan]

Eliminating Non-Generating Symbol N

The variable only has the production , meaning it never derives a terminal string. is non-generating. Eliminating removes all rules referencing :

Eliminating Null Production L → ε
Eliminating Unit Production L → M
Isolating Terminals

Introduce :

Answer:

The resulting CNF grammar is:


Exercise Set: CFG Simplification, CNF & GNF

Exercise Questions: Simplification, CNF & GNF

Question 1

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:

  1. Single Terminal Prefix: Every production step generates exactly one terminal symbol at the leftmost position of the sentential form ().
  2. 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.
  3. 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:

  1. Eliminate -productions, unit productions, and useless symbols.
  2. Order variables as such that if , then .
  3. Eliminate immediate left recursion () by introducing a new variable .
  4. 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.

Answer:

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.

Question 2

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:

  1. Elimination of -productions (null productions).
  2. Elimination of unit productions (rules of the form ).
  3. Elimination of useless symbols (non-generating first, then unreachable).

Eliminating Null and Unit Productions:

  1. 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 ).
  2. 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:

  1. 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.
  2. 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.
Answer:

Simplification of a CFG is performed in three distinct phases:

  1. Elimination of -productions: nullable variables are determined and productions are expanded without .
  2. Elimination of unit productions: transitive unit chains are resolved by replacing unit rules with the non-unit production bodies of .
  3. Elimination of useless symbols: non-generating symbols are eliminated first, followed by unreachable symbols.

Past exam questions for Theory of Computation

← CFG, Derivations, Parse Trees & AmbiguityCFL Closure, Pumping Lemma & Decision Algorithms →