The finite state machine given in figure below recognizes :

1. Aany string of odd number of a’s
2. Bany string of odd number of b’s
3. Cany string of even number of a’s and odd number of b’s
4. Dany string of odd number of a’s and odd number of b’s

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

Show answer & explanation

Correct answer: D. any string of odd number of a’s and odd number of b’s

Explanation

Horizontal a-edges flip a-parity and vertical b-edges flip b-parity. The start state is (even a, even b) and the accepting state, diagonally opposite, is (odd a, odd b).