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

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
- Let L= {ab, aa, baa}. Which of the following strings are not in L*?
- Let A={a, b} and L=A*. Let X={anbn, n>0}. The languages L U X and X are respectively :
- Which of the following symbol table implementations is best suited if access time is to be minimum?
- The sum of minimum and maximum number of final states for a Deterministic Finite Automata (DFA) having ' P ' state is equal to :
- Three address codes can be represented in special structures known as : (A) Quadruples (B) Triples (C) Patterns (D) Indirect Triples
- Which of the statement is/are CORRECT ? (A) Moore and Mealy machines are finite state machines with output capabilities. (B) Any given Moor…