Which of the following finite automata recognize L = {a, b}*? (Transition tables A–D are shown; in each, the start state q0 is accepting.)
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 is accepting and has a transition back to itself (or to accepting states) on both a and b, so every string over {a, b} can be read while staying in an accepting state. States that cannot be reached do not change the language, so all four accept {a, b}*.
More Theory of Computation and Compilers questions
- Match List I with List II
- Consider the following statements: (A) For every regular language, we can design Turing Machine (B) For every context free language, we can…
- The transition function ' ' in multi-tape Turing machine is defined as:
- In Pumping Lemma for regular languages, to say a language is satistying pumping lemma, what is the mınımum length of ' y ' if you consider…
- The item generated by the production is :
- In the ε-NFA M = ({q0, q1, q2, q3}, {a}, δ, q0, {q3}) with δ: q0 –ε→ q1, q1 –ε→ q2, q2 –a→ {q2, q3}, and no other moves, what is the minimu…