All mock tests are FREE till 31 December — register to save your progress
Unit 8 · Theory of Computation and Compilers Paper 2 CS · June 2024 (Cancelled)

For the given two machines which of the following is correct?

Figure

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

Show answer & explanation

Correct answer: C. both are equivalent Machines

Explanation

The second machine accepts a(a + b)*. The first is an NFA (A has two moves on a): a string must start with a; whenever it ends in a, the path can stay in A and take the last a to B, and whenever it ends in b it can sit in B. So it also accepts exactly a(a + b)*. The machines are equivalent (and not both DFAs).

Note on the official key: the official key says option B. Official/PW key is B (non-equivalent). Tracing both machines shows each accepts exactly the strings that start with a.

More Theory of Computation and Compilers questions