Two finite state machines are said to be equivalent if they :
2018
Two finite state machines are said to be equivalent if they :
- A.
Have the same number of edges
- B.
Have the same number of states
- C.
Recognize the same set of tokens
- D.
Have the same number of states and edges
Attempted by 238 students.
Show answer & explanation
Correct answer: C
Definition: Two finite state machines are equivalent if they recognize the same language.
That means for every input string w, either both machines accept w or both reject w.
Formal condition: for all strings w, M1 accepts w iff M2 accepts w.
Common methods to check equivalence: convert both to minimal deterministic automata and compare them up to renaming of states, or build the product automaton to test whether the symmetric difference of the languages is empty.
Note on wording: the option says "tokens" but here it should be understood as the set of input strings (the language) recognized by the machines.
A video solution is available for this question — log in and enroll to watch it.