COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
Which one of the following is not a Greibach Normal form grammar?(i) S
|
|
(i) and (ii)
|
|
|
(i) and (iii)
|
|
|
(ii) and (iii)
|
|
|
(i), (ii) and (iii)
|
Explanation:
Detailed explanation-1: -A context-free grammar (CFG) is in Greibach normal form (GNF) if and only all of its production rules meet one of the criteria listed below: A non-terminal that generates a terminal.
Detailed explanation-2: -For example: G1 = S → aAB | aB, A → aA| a, B → bB | b G2 = S → aAB | aB, A → aA | , B → bB |
Detailed explanation-3: -The grammar G1 is in CNF as production rules satisfy the rules specified for CNF so it can be directly used to convert to GNF. According to the rules G1 is also in GNF form.
Detailed explanation-4: -CFG. Context-free Grammar Derivation Derivation Tree Ambiguity in Grammar Unambiguous Grammar Simplification of CFG Chomsky’s Normal Form (CNF) Greibach Normal Form (GNF)
There is 1 question to complete.