For the given two machines over {a, b}, which of the following is correct?
Machine 1: states A (start), B (final); A –a→ A, A –a→ B, B –b→ B, B –b→ A.
Machine 2: states A (start), B (final), C (final); A –a→ B, B –a→ B, B –b→ C, C –b→ C, C –a→ B.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. Both are equivalent machines
Explanation
Machine 1 is an NFA (two a-moves from A). After the first 'a' its set of active states is always {A, B}, which contains the final state B, so it accepts every string beginning with a: a(a + b)*. In Machine 2 every string beginning with a ends in B or C, both final, and strings beginning with b are rejected, so it also accepts a(a + b)*. The machines are equivalent. (Some published keys print 'non-equivalent', but the languages are identical.)More Theory of Computation and Compilers questions
- The number of tokens in the line ' for i in range (begin; end ; step) : ' is:
- In the pumping lemma for context-free languages, for a string uvwxy, what is the minimum length of vx together?
- Which of the following is an ε-free grammar?
- While processing a string, an LR parser reads the input
- What are the minimum and maximum numbers of initial, dead, unreachable and final states in a valid n-state finite automaton whose accepted…
- 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…