Design a DFA with following condition.

Question

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

Answer 1

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} $$

Answer 2

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.