Discussion
Consider the context free grammar with productions :
\(S \rightarrow ABa\)
\(A \rightarrow aab\)
\(B \rightarrow Ac\)
After constructing an equivalent grammar in Chomsky Normal form, the resulting grammar will contain ..............productions.
Answer: B
The Chomsky Normal Form grammar has 8 productions.
In CNF every production is either \(A \rightarrow BC\) or \(A \rightarrow a\). Introduce a variable for each terminal and break the long right-hand sides into pairs:
\[ \begin{aligned} S &\rightarrow A X_1, \quad X_1 \rightarrow B T_a \\ A &\rightarrow T_a X_2, \quad X_2 \rightarrow T_a T_b \\ B &\rightarrow A T_c \\ T_a &\rightarrow a, \ T_b \rightarrow b, \ T_c \rightarrow c \end{aligned} \]
That is 2 for S, 2 for A, 1 for B and 3 terminal productions: 8 in all. The grammar has no null or unit productions to remove first. Six productions are too few once the two length-3 right-hand sides are split into pairs, and 9 or 10 would include productions CNF does not need.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development