Which of the following languages are not regular? A. L = {(01)ⁿ0ᵏ | n > k, k ≥ 0} B. L = {cⁿbᵏaⁿ⁺ᵏ | n ≥ 0, k ≥ 0} C. L = {0ⁿ1ᵏ | n ≠ k}
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. A, B and C
Explanation
Each needs an unbounded counter to compare two quantities (n > k; matching the a's to n + k; n ≠ k), which a finite automaton cannot do. All three are non-regular.
More Theory of Computation and Compilers questions
- Any string of terminals generated by the CFG S → XY, X → 0X | 1X | 0, Y → Y0 | Y1 | 0 (S is the start symbol)
- Let L1 = {0ⁿ1ⁿ0ᵐ | n ≥ 1, m ≥ 1}, L2 = {0ⁿ1ᵐ0ᵐ | n ≥ 1, m ≥ 1}, L3 = {0ⁿ1ⁿ0ⁿ | n ≥ 1}. Which are correct? A. L3 = L1 ∩ L2. B. L1 and L2 are…
- Given below are two statements Statement I: The family of context free languages is closed under homomorphism Statement II: The family of c…
- What is the minimum number of states required to the finite automaton equivalent to the transition diagram given below?
- Find the regular expression for the language accepted by the automata given below.
- What language is accepted by the PDA M = ({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2}) where in q0 every input symbol is pushed, δ(q0,…