0

A DFA that accepts a language in which every odd position of a string is a 1 with inputs as {0,1}

annie
  • 1
  • 1 ( ( 0 | 1 ) 1 ) * – DanielV May 04 '14 at 09:30
  • @Daniel, that's a description of the language, not a DFA. But maybe you are hinting that from that description of the language, it should be easy to construct the DFA. – Gerry Myerson May 04 '14 at 09:50
  • 1
    @GerryMyerson Well I took it for granted all regex are equivalent to DFA, but then again, I can see in hindsight how that is a bad assumption to apply to a question like this. – DanielV May 04 '14 at 10:09

2 Answers2

2

You can do this in 2 states - WAIT and OK. You start in the WAIT state and hope to get to the OK state, which accepts. Here are the rules: $$ \mathrm{WAIT} \overset{1}{\rightarrow} \mathrm{OK} $$ $$ \mathrm{OK} \overset{0}{\rightarrow} \mathrm{WAIT} $$ $$ \mathrm{OK} \overset{1}{\rightarrow} \mathrm{WAIT} $$

Piotr Miś
  • 569
  • And if you're in the WAIT state, and see a zero? I guess there's a "black hole" state, and the convention is not to count it as a state? – Gerry Myerson May 04 '14 at 09:53
  • 2
    That rises an error - the DFA does not accept the input. You can convert the description into a complete DFA by adding ERROR state you mention, but I find that it only clutters the automaton. – Piotr Miś May 04 '14 at 09:57
0

State Machine

All state machines have a starting point. The top right state represents the "never going to accept" state. The bottom left state is the necessary accepting state. The other state is the "seen an even number of inputs and so far so good" state.

DanielV
  • 23,556