The Binary BrothersTwo Mentors, One Mission – Your Selection
All mock tests are FREE till 31 December — register to save your progress
Unit 8 · Theory of Computation and Compilers Paper 2 CS · December 2022 Shift 1

Which of the following finite automata recognise the language L = {a, b}*?
A. M = ({q0}, {a, b}, δ, q0, {q0}) with δ(q0, a) = {q0}, δ(q0, b) = {q0}
B. M = ({q0, q1}, {a, b}, δ, q0, {q0, q1}) with δ(q0, a) = δ(q0, b) = {q0, q1}, δ(q1, a) = δ(q1, b) = {q1}
C. M = ({q0, q1}, {a, b}, δ, q0, {q0, q1}) with δ(q0, a) = {q0, q1}, δ(q0, b) = {q0}, δ(q1, a) = –, δ(q1, b) = {q1}
D. M = ({q0, q1, q2}, {a, b}, δ, q0, {q0}) with δ(q0, a) = δ(q0, b) = {q0}, δ(q1, a) = {q2}, δ(q1, b) = –, δ(q2, a) = {q0}, δ(q2, b) = {q2}

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: D. A, B, C and D

Explanation

In every machine the start state q0 is final and loops on both a and b (or can always stay in a final state), so every string over {a, b} is accepted. In D, the states q1 and q2 are unreachable and don't matter.

More Theory of Computation and Compilers questions