0
$\begingroup$

Text

Been mulling over this one for hours, my initial thought was { w ε {a,b}* | w is empty, or ends with either ab or ba} but that's clearly wrong as neither aba nor bab are accepted by the automaton. If anyone has any idea what language this automaton accepts it would really put my mind at ease.

$\endgroup$
3
$\begingroup$

$(a^+b \mid b^+a)^*$. I am not sure there is a "simple" description of your language in plain English, but directly from the regex you get that it is the language that has the empty string and all strings that can be partitioned in such a way that each part is either multiple $a$'s (at least one) followed by one $b$, or vice versa.

In my opinion the regex and the automaton describe the language better than a "natural language description" in this case.

$\endgroup$
0

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.