So in my attempt to convert the following DFA into a regular expression, I ended up with ((ba)*(ab(ab)*)*(aa(ba)*a)*)*. The exercise I'm following wants me to convert the DFA into a regular expression then describe its language in plain English, however, I can't seem to come up with anything for the converted expression. Any hints on how to go from here?

DFA in question

  • 1
    $\begingroup$ It's not a simple task. One thing I notice is that you can't have two B's in a row. Anything else? Also, your regular expression seems wrong because aaaba matches the DFA but not the regex $\endgroup$
    – user253751
    Aug 26, 2022 at 22:48
  • $\begingroup$ Yeah, I also noticed the part about no bb's, but I'm not sure about any other pattern. I tried redoing the regex but I'm still quite lost ^^" $\endgroup$
    – apollonia
    Aug 27, 2022 at 5:32

1 Answer 1


To accept a string, you must start in $q_0$ and end in $q_0$ or in $q_3$.
A path from $q_0$ to $q_0$ can make a cycle through $q_5$ (so you can have $(ba)^*$) or through $q_1,q_2,q_3,q_4$ (and so $a(ba)^*a(ba)^*a$), and then you can put these together to obtain $((ba)^*+a(ba)^*a(ba)^*a)^*$.
A path from $q_0$ to $q_3$ is a path from $q_0$ to $q_0$ and then a path that do not pass twice through $q_0$ from $q_0$ to $q_3$, i.e. $ab(ab)^*$.

Now, we can put all together: $$((ba)^*+a(ba)^*a(ba)^*a)^*(\varepsilon+(ab)^+)$$

A description of this language in plain English could be something like this: strings of the type $((ba)^*+a(ba)^*a(ba)^*a)^*$ or $((ba)^*+a(ba)^*a(ba)^*a)^*(ab)^+$. The first type if formed by strings starting either with $a$ or $b$, with no consecutive $b$s, such that the number $a$s exceeds the number of $b$s by a multiple of 3 (0 included), and ending with $a$; the second type if formed by strings of the first type concatenated with $(ab)^+$, so with a nonempty string starting with $a$, ending with $b$ and such that no two consecutive letters are equal.

Here is the simplest description: strings without consecutive $b$s such that the number $a$s exceeds the number of $b$s by a multiple of 3 (0 included).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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