COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
Match the following a. Chomsky Normal form i. S
|
|
iv iii i i
|
|
|
iv iii ii i
|
|
|
iii iv i ii
|
|
|
iii iv ii i
|
Explanation:
Detailed explanation-1: -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-2: -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-3: -For example: G1 = S → aAB | aB, A → aA| a, B → bB | b G2 = S → aAB | aB, A → aA | , B → bB |
There is 1 question to complete.