Consider the language L = {w ∈ {a, b, c}* : nₐ(w) + n_b(w) = n_c(w)}. L is
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. Context free but not linear
Explanation
A PDA can push for each a or b and pop for each c (with sign handling), so L is context-free. Because the symbols can occur in any order, L is not generated by a linear grammar (the keyed answer).More Theory of Computation and Compilers questions
- 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?
- A compiler for a high-level language that runs on one machine and produces code for another machine is called a