[Solved]: construct a dfa that accepts odd consecutive number of 0's and 1's

Problem Detail: 

this dfa should accept only consecutive odd number of both 0's and 1's. example: 10001,1110001,10,01,011101.

How can I draw its diagram?

Asked By : user49697

Answered By : Rick Decker

Here are a couple of hints to get you started.

1. Could you make a DFA that accepts only $0, 000, 00000,\dotsc$? You can do it with a start state, a final state, and one other non-final state.
2. Obviously, if you can do (1), you can make a DFA that accepts only $1, 111, 11111,\dotsc$.
3. Merge the two DFAs into one with a common start state and appropriately link the two final states. You'll have a DFA that accepts all strings which have an odd number of consecutive $0$s followed by an odd number of consecutive $1$s, followed by ... or an odd number of consecutive $1$s followed by an odd number of consective $0$s, followed by ... , which is what you want.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56088

 Ask a Question

 Download Related Notes/Documents