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.
Draw a DFA for (a|ba)(a|ba)*
automataregular expressionsregular-language
Related Solutions
(A)
$\{a^mb^n : m,n \ge 0\}$ is not-regualr if $m,n$ have any relation between them.Such that,
$m=n$
$m\ne n$
$m\ge n$
$m\le n$ etc.
(B)
But if $m,n $ have not any relation then it will be regular language and it could be read as string with any number of $a$ followed by any number of $b$.
For your knowledge let's take an example,
$L_1=\{a^n:n\ge 0\}$
$L_2=\{b^n:n\ge 0\}$
then what is $L_1.L_2$(concat)?
It will not be $\{a^nb^n : n \ge 0\}$,it will be any number of $a$ followed by any number of $b$.
I hope it can help you
Language consist of :
- $\epsilon$
- strings of just b's
- and strings such that every a is immediately followed by b $$L=\{\epsilon,b,bb,bbb,...,ab,abb,....,bab,bbababb,.... \}$$ Regular expression: $(b^*\,ab\, b^*)^*+b^*$
DFA that accepts L :
Best Answer
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.
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.