1 Crore+ students have signed up on EduRev. Have you? 
One of the uses of CNF is to turn parse tree into:
CNF (Chomsky’s normal form). A grammar is in the form of CNF is as follows:
S → AB
S → a
Where A, B are nonterminals and a is the terminal.
All productions should be of length 2.
Which of the following grammar is in Greibach Normal Form?
A. S → AB, A → a, B → b
B. S → aA  A → ϵ
C. S → Aa, A → a
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 (nonterminal)
What is the minimum number of productions present in the below given context free grammar to make it Chomsky Normal Form?
S → XYx
X → xxy
Y → Xz
Concepts:
A contextfree 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(nonterminal) and a is terminal
Calculation:
S → XA
A → YB
B → x
X → BC
C → BD
D → y
Y → XE
E → z
A CFG (Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A → BC or A → a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is
Concept:
A contextfree 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(nonterminal) 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
Let G = (V, T, S, P) be any contextfree grammar without any λproductions or unit productions. Let K be the maximum number of symbols on the right of any production in P. The maximum number of production rules for any equivalent grammar in Chomsky normal form is given by:
Where ⋅ denotes the cardinality of the set.
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 nonterminal symbol generating two nonterminals. For example, S > AB
3. A non terminal generating a terminal. Example: S > a
To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is:
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:
2n – 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
What is the minimum number of productions needed to add to the below given context free grammar to make it Greibech Normal Form?
S → aSb  ab  bb
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.
If L(G) is accepted by pushdown automaton and x is a string of length 21 in L(G), how long is a derivative of x in G, if G is Chomsky normal form?
Chomsky normal form
S → AB
A → a
B → b
Length of string = x
Length of the derivate of string x in context free grammar:
2x – 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
If a Context Free Grammar G is in Chomsky Normal Form, to derive a string of length 101 number of productions needed is _____.
Concepts:
A contextfree 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(nonterminal) 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
Let G be a Context Free Grammar in Chomsky Normal Form. To derive a string (aaaaaa)n where a is terminal variable and n is 5, the number of products to be used is _____.
Concepts:
A contextfree 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(nonterminal) and a is terminal
Data:
Since n = 5
(aaaaaa)^{5}
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
18 videos56 docs41 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
18 videos56 docs41 tests








