Which of the following languages can be recognized by a Non-Deterministic Finite Automaton (NFA) but cannot be recognized by a Deterministic Finite Automaton (DFA)?
(A) L₁ = {w ∈ {0,1}* | the length of w is even}
(B) L₂ = {w ∈ {0,1}* | the length of w is odd}
(C) L₃ = {w ∈ {0,1}* | all 0's come before all 1's in w}
(D) L₄ = {w ∈ {0,1}* | w contains an equal number of 0's and 1's}
(E) L₅ = {w ∈ {0,1}* | all 1's come before all 0's in w}
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. None of the above
Explanation
NFAs and DFAs recognise exactly the same class (regular languages). No language is accepted by an NFA but not by any DFA. (L₄ is not regular, so neither can accept it.)More Theory of Computation and Compilers questions
- Arrange the following phases in the correct order as they typically occur in the compilation process. (A) Lexical Analysis (B) Semantic Ana…
- Arrange the following language classes in ascending order of their expressive power, as defined by the Chomsky hierarchy: (A) Context-free…
- Which of the following are context-free languages? (A) {wⁱ xʲ yᵏ zˡ | i + k = j + l, where i, j, k, l ≥ 0} (B) {wⁱ xʲ yᵏ zˡ | i = j, k = l,…
- Let L = {ab, aa, baa}. Which of the following strings is NOT in L*?
- Let A = {a, b} and L = A*. Let X = {aⁿbⁿ | n > 0}. The languages L ∪ X and X are respectively:
- Which of the following symbol-table implementations is best suited if access time is to be minimum?