The maximum yield length of the following CNF CFG is
S → AB
A → CD
B → e
C → a
D → b
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. 4
Explanation
The longest root-to-leaf path is S → A → C → a. For a CNF parse tree whose longest path has 3 variables, the yield has at most 2³⁻¹ = 4 terminals. This bound is the keyed answer; the only string actually derived, 'abe', has length 3.More Theory of Computation and Compilers questions
- Consider the language L = {w ∈ {a, b, c}* : nₐ(w) + n_b(w) = n_c(w)}. L is
- Consider the following statements: A. A context-free language is generated by an LR(0) grammar if and only if it is accepted by a determini…
- Which phase of the compiler checks the grammar of the program?
- Consider the following statements: A. The set of Turing machine codes for TMs that accept all inputs that are palindromes (possibly along w…
- Which of the following parsers is the most powerful?
- Which of the following statements is correct?