# Describing the Language of a DFA with 7 States

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?

• 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 Aug 26, 2022 at 22:48
• 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 ^^" Aug 27, 2022 at 5:32

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).