Test: Normal Forms of Context Free Grammar - Computer Science Engineering (CSE) MCQ

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)*.
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

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. 

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

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

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

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

A context free grammar is in Greibach Normal Form if the right hand sides of all the production rules start with a terminal, optionally followed by some variables.

Conversely, every context frr grammar can be converted into Chomsky Normal form and to other forms.

The correct format: A->BC, A->a, X->e.

According to the number of terminals present in the grammar, we need the corresponding that number of terminal variables while conversion.

When the production in G satisfy certain restrictions, then G is said to be in ‘normal form’.