Multiple choice

Which of the following is not true for deterministic context free languages?

  1. Deterministic context-free languages can be recognized by a deterministic turing machine.

  2. They are a proper subset of context-free languages.

  3. They can be accepted by a deterministic pushdown automaton.

  4. They are closed under union.

  5. They are closed under complement.
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

 DCFL is a subset of the complexity class SC. The set of deterministic context-free languages is not closed under union but is closed under complement.

Keep practicing — related questions