COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
1) A
|
|
|
2) A
|
|
|
3) A
|
|
|
Both 1) and 2)
|
Detailed explanation-1: -Explanation: The normal form is of the format: A->aB where the right hand side production tends to begin with a terminal symbo, thus having no left recursions.
Detailed explanation-2: -Chomsky Normal Form: Productions are of the form A → BC or A → a, where A, B, C are variables and a is a terminal symbol. Greibach Normal Form Productions are of the form A → a, where ∈ V ∗ and A ∈ V .
Detailed explanation-3: -CNF stands for Chomsky normal form. A CFG(context free grammar) is in CNF(Chomsky normal form) if all production rules satisfy one of the following conditions: Start symbol generating . For example, A → .
Detailed explanation-4: -Chomsky’s Normal Form Stands as CNF. A context free grammar is in CNF, if the production rules satisfy one of the following conditions. If there is start Symbol generating . Example − A-> If a non-terminal generates two non-terminals.
Detailed explanation-5: -To be in CNF, all the productions must derive either two non-terminals or a single terminal. CNF restricts the number of symbols on the right side of a production to be two. The two symbols must be non-terminals or a single terminal.