Normal Forms of Context Free Grammar - MCQ Test with solutions for GATE

CNF (Chomsky’s normal form). A grammar is in the form of CNF is as follows:
S → AB
S → a
Where A, B are non-terminals and a is the terminal.
All productions should be of length 2.

• In this, first eliminate useless symbols for CNF. Eliminate the null productions and unit productions.
• In CFL it is possible to find atmost two short substrings that we can pump i times for any integer i.
• Pumping Lemma for CFL is used to examine the size of parse trees. One of the uses of CNF is to turn the parse into binary trees. 

A context grammar is said to be in Greibech Normal Form if all the productions have the form
S → xA
where x ϵ T and x ϵ V*
T is terminal and V is variable (non-terminal)

• Option A: Not in GNF. Since production S → AB is not in GNF
• Option B: Not in GNF. Since production A → ϵ is not in GNF
• Option C: Not in GNF. Since production S → Aa is not in GNF

Concepts:
A context-free grammar is in Chomsky Normal Form if all productions are of the form
A → BC or A → a
{A, B, C} ϵ V and a ϵ T
V is variable(non-terminal) and a is terminal

Calculation:
S → XA
A → YB
B → x
X → BC
C → BD
D → y
Y → XE
E → z

Concept:
A context-free grammar is in Chomsky Normal Form if all productions are of the form
A → BC or A → a
{A, B, C} ϵ V and a ϵ T
V is variable(non-terminal) and a is terminal

Formula:
n = 2x - 1
number of productions required to generates string of length x.
where x is the length of the string

Example:
Production:
S → XY
X → a
Y → b
Derive the string ab
S → XY
S → aY
S → ab
Number of productions needed = 3
Verification
2x - 1 = 2(2) - 1 = 3

Concept:
Context free grammar : A grammar G = (V, T ,S, P) is said to be context- free if all productions in P have the form A -> x where A ϵ V and x ϵ (V U T)*.

Explanation:
If context free grammar G = (V, T, S, P) is without λ-productions or unit productions.
K = maximum number of symbols on right side of production.
The maximum number of production rules for equivalent grammar in CNF:
(K - 1)|P| + |T|
A context free grammar is in CNF (Chomsky normal form) if it satisfies these conditions:
1. Should not contains null or unit productions.
2. A non-terminal symbol generating two non-terminals. For example, S -> AB
3. A non- terminal generating a terminal. Example: S -> a

Concept:
Chomsky normal form
S → AB
A → a
B → b
Length of string = n

Length of the derivate of string n in context free grammar:
2|n| – 1

Example:
If we need to generate ab (string of length 2)
S → AB
S → aB
S → ab
Number of steps = 2 × 2 – 1 = 3

Concepts:
A context grammar is said to be in Greibech Normal Form if all the productions have the form
S → xA
where x ϵ T and A ϵ V*

Calculation:
S → aSB | aB | bB
B → b
The minimum number of productions added is 1.

Chomsky normal form
S → AB
A → a
B → b
Length of string = |x|

Length of the derivate of string x in context free grammar:
2|x| – 1 = 2 × 21 - 1 = 41

Note:
Question say steps needed to generated string of 10 length
e.g. if we need to generate ab (string of length 2)
S → AB
S → aB
S → ab
Number of steps = 2× 2 – 1 = 3

Concepts:
A context-free grammar is in Chomsky Normal Form if all productions are of the form
A → BC or A → a
{A, B, C} ϵ V and a ϵ T
V is variable(non-terminal) and a is terminal

Data:
x = 101
n → number of productions required to generates string of length x.

Formula:
n = 2x – 1

where x is the length of the string

Calculation:
n = 2(101) – 1
∴ n = 201

Concepts:
A context-free grammar is in Chomsky Normal Form if all productions are of the form
A → BC or A → a
{A, B, C} ϵ V and a ϵ T
V is variable(non-terminal) and a is terminal

Data:
Since n = 5
(aaaaaa)⁵
Length of string = x = 30

Formula:
The number of products used = 2x – 1
where x is the length of the string

Calculation:
number of products = 2x – 1 = 2 × 30 – 1 = 59