So i have some theory of computer science homework and I'm struggling with this question currently. I am given the following automaton:

  • $Q = \{q_0,q_1\}$.
  • $\Sigma = \{a,b\}$.
  • $q_0 = q_0$.
  • $F = \{q_0\}$.
  • $\delta(q_0,a) = \delta(q_0,b) = q_1$, $\delta(q_1,a) = \delta(q_1,b) = q_0$.

I have to do two things: draw a state diagram, and write an equivalent regular expression. For now, these are my answers. I think my diagram is correct, but I'm not sure about the regular expression.

State diagram answer

My regular expression for now is $(a+b)^*(a+b)$. Any help is very much appreciated.

  • 1
    $\begingroup$ The language of your automaton is all words of even length. In contrast, your regular expression accepts all words of positive length. $\endgroup$ Apr 8 at 7:31
  • $\begingroup$ Yes, it's even length of words. I've traced it but I cant figure out an expression for it. So far this is what i have in mind: (aa + ab + ba + bb)* or ( (a+b)(a+b) )* $\endgroup$ Apr 8 at 7:52
  • $\begingroup$ Both of these work. $\endgroup$ Apr 8 at 7:53
  • $\begingroup$ Thanks, i think i got it now! $\endgroup$ Apr 8 at 8:54

Your automaton accepts all words of even length, whereas your regular expression accepts all words of positive length. The most common way to express the language of all words of even length as a regular expression is $(\Sigma\Sigma)^*$, where $\Sigma$ is a common shortcut for an arbitrary letter of the alphabet (in your case, $\Sigma$ stands for $a+b$).


Let $r$ be regular expression of your automaton, so $$r=\lambda\cup\left((a\cup b)(a\cup b)\right)^+.$$


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.