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 non-terminals 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 (non-terminal)
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 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
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 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
Let G = (V, T, S, P) be any context-free 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 non-terminal symbol generating two non-terminals. 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:
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
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:
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
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 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
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 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)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 videos|56 docs|41 tests
|
Use Code STAYHOME200 and get INR 200 additional OFF
|
Use Coupon Code |
18 videos|56 docs|41 tests
|
|
|
|
|
|
|
|
|