0
$\begingroup$

I met a question concerning draw a DFA for $\left(a\vert ba\right)\left(a\vert ba\right)^\ast$.
I firstly tried to expand the regular expression to a $\varepsilon$-NFA, then plan to transform it to a DFA. However, I feel there is something wrong when I expand $\left(ba\right)^\ast$. Because when I use the closure method to convert my $\varepsilon$-NFA to DFA, some states could not accept b, so even I draw the 'DFA', it may be not the correct DFA.
So is it a normal situation under this $\left(ba\right)^\ast$ condition? Or it is because where I got wrong? Please tell me if you have any thoughts, thank you!
The following is what I have tried for your kind reference. my trying

$\endgroup$
1
  • $\begingroup$ Hi, as I said in the same question that you posted a while ago, all you need to do is to add a "reject" state to $q_1$ that rejects any strings with $bb$ in them ($q_1$, reading $b$, goes to $q_2$ which is non-accepting, and q_2, reading anything, stays in $q_2$). math.stackexchange.com/questions/3324704/… $\endgroup$
    – marcelgoh
    Aug 16 '19 at 7:25
1
$\begingroup$

Here is a solution. The double circled state is the only accept state. The start state is the one with a nondescript arrow going into it.

enter image description here

As you can see, once two $b$'s follow each other directly, we go to the lower right state, from which no escape is possible. Any other string that is nonempty and ends with an $a$ gets accepted.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.