26. What is meant by a Unit Production?
Any production of a CFG of the form
A B
→
where A B V
, ∈ is called a ‘Unit Production’.
27. State the procedure to remove the unit productions.
(i) Find all variables B, for each A such that
A B
⇒
*
This is done by sketching a “dependency graph” with an edge
(C, D) whenever the grammar has unit production C
D
→ ,
then A B
⇒
*
holds whenever there is a walk between A and B.
(ii) The new grammar $
G, equivalent to G is obtained by letting
into $
P all non-unit productions of P.
(iii) Then for all A and B satisfying A B
⇒
*
, we add to $
P
A
y y
y n
→ 1 2
| |
|
KK
where B
y y
y n
→ 1 2
| |
|
KK
is the set of all rules in $
P with B
on the left.
28. What do you mean by left recursion?
A variable A is left-recursive if it occurs in a production of the form
A
Ax
→
for any x V T
∈ ∪
(
)
* .
A grammar is left-recursive if it contains at least one
left-recursive variable.
29. Can every CF language be represented by a grammar that is not
left-recursive?
YES.
30. What are the kinds of Normal Forms?
There are two kinds of Normal Forms viz.,
(a) Chomsky Normal Form (CNF)
(b) Greibach Normal Form (GNF)
31. What do you mean by Chomsky Normal Form?
A CFG without any λ-production is generated by a grammar in
which productions are of the form A BC
A a
→
→
or
, where A B V N
, ∈
and a V T
∈ .
32. Differentiate between Chomsky’s Normal Form (CNF) and Greibach
Normal Form (GNF).
Con text-free Grammars
157