Designing a DFA to accept a string

375 Views Asked by At

enter image description here

I have created the following FA

enter image description here

Im i correct?

1

There are 1 best solutions below

8
On BEST ANSWER

Almost. But your DFA doesn't accept $00010$. In fact, if the DFA accepts $a0b1w$ where $a,b\in \{0,1\}$ and $w\in \{0,1\}^*$, then $\lvert w\rvert$ is a multiple of $4$. In fact the language of your DFA is $((0+1)0(0+1)1)^+$ i.e. $(.0.1)^+$ where "$.$" is "any symbol", i.e. $(0+1)$.

Fortunately, this is easily fixed: instead of transitioning from state $F$ to $B$ on any symbol, instead make the transitions $F\stackrel{0,1}\to F$. Once the machine reaches $F$, it never leaves (for any suffix $w$ of an input of the form $a0b1w$).