Question

--Question For Automata and Pattern Matching

--

Show that there is an algorithm which receives as input a DFA M over the alphabet {0, 1}

and decides whether M recognises exactly the binary strings that contain an odd number of 1’s.
Clearly state all results proven in class that you’ve used (without proof).

Answer 1

It is known that there is an algorithm deciding whether 2 DFA'S, M, M' accept the same language. The language {w elementof {0, 1} */w contains an odd no. of 1's } is accepted by the DFA m'. So, we can apply the above algorithm to the DFAs M and M' to decide whether L(m) = L(m')