Which of the following statements is incorrect?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. Given a context free language L, its complement is also context free.
Explanation
The CFG membership problem (is x in L(G)?) is decidable in polynomial time (e.g. O(n³) with the CYK algorithm), so statement (1) is true. Context-free languages are not closed under complementation in general, so statement (2), which claims the complement of every CFL is itself a CFL, is false – this is the incorrect statement. The language in (3) is a classic textbook example (Hopcroft-Ullman) of a context-free language that is provably not deterministic context-free, so (3) is a true statement.More Theory of Computation and Compilers questions
- The minimum state DFA of the following would be the following: (a DFA with states q0 (start), q1, q2, q3 and q4 (accepting) is given, with…
- Find the Follow (A) & Follow (C).
- In the LL(1) Parsing table of the given CFG, how many valid non-blank entries will be there in the rows for variables 'B' and 'D'?
- Identify the correct statement from the following.
- What will be the FIRST(S) & FIRST(D)?
- The I0 state of the canonical LR(0) set of the SLR(1) parser of this CFG has how many productions?