0

Alphabet ${} = \{0,1\}$.

Language $L = \{ w \in \{0,1\}^* \mid \text{ number of $0$'s in $w$ is even and after every $1$ goes $0$} \}$.

I'm trying to create DFA that accepts language $L$. But I have some problems. Transition arrow with $1$ can only lead to the same state is goes from. But when it happens this state can not be final state. If arrow with $1$ goes to another state, then word can contain $11$ so this DFA would not accept this language. Probably I think in incorrect way? Can you give some advice how to create DFA that will accept language $L$?

Community
  • 1
user2950602
  • 53
  • Check out the proof that regular languages $L, M$ have $L\cap M$ regular, which gives an explict DFA. (Or, rather, it deals with $NDFAs$ or $\epsilon$-NDFAs, but the usual proof that any language recognizable by those automata is also recognizable by a DFA also gives an explicit construction.) Basically, you setup the product DFA (with states, transitions, etc. being exactly what you'd expect), and accept states that are the product of acceptable states in $L$ and $M$. – anomaly Oct 29 '14 at 19:05

2 Answers2

1

The regular language of even zeros is the language $(1*01*01*)*$, the regular language for no consecutive ones is $(1?0*)*$. One can construct $\varepsilon$-NFAs for each case using the Thompson construction, and use the subset construction to convert them into two explicit DFAs. One can then use the (constructive) proof that the finite union of two regular languages is regular to get an explicit DFA that matches both.

MT_
  • 19,603
  • 9
  • 40
  • 81
0

For the first part of the conditions, i.e. $|w|_0\equiv 0 \pmod 2$, you need two states, one for when the number of $0$'s read is even and one for the odd. For the second one, you must create a help state for the two states you had that reads the $1$ and pushs the 0 for the other state.

So the problem is that you are thinking in just keep 2 states. And you said that
"If arrow with 1 goes to another state, then word can contain 11 so this DFA would not accept this language" that is not necessary true, you can create a junk state where that kind of things go.

Hope it helps.

Phicar
  • 14,722