Which of the following CFG(s) is/are in Chomsky Normal Form? (All capital letters are variables & lower case letters are terminals)
A. S → ABC | AB, A → a, B → b, C → d
B. X → RT | TR, T → t, R → XT | r
C. P → qP | sQ, Q → r | s
D. M → MN | MP, N → nm | n, P → p
Choose the correct answer from the options given below:
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. B only
Explanation
In CNF every rule is A → BC or A → a. A has S → ABC (three variables). C has P → qP (terminal + variable). D has N → nm (two terminals). Only B satisfies CNF.More Theory of Computation and Compilers questions
- yacc is which of the following parsers?
- For the above-mentioned passage, which of the following automata is correct? Each option is described by its transitions (start state 1).
- For the above specified passage, which of the following represents the grammar for the language accepted by the machine?
- Which of the following represents the minimum-state DFA for the above specified passage?
- For the above specified passage, which of the following is a DFA for the language accepted by the machine?
- For the above specified passage, which of the following represents the regular expression?