Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3 / b

The formal language is a regular language. A regular expression for it isThe first Kleene star independently chooses $m$ copies of the word $ab$, and the second independently chooses $n$ copies of $bc$. Their concatenation produces exactly the required words. Either count may be zero, including both counts zero, which gives the empty word. By Kleene theorem, the regular expression establishes regularity.

The formal language is not a regular language. Let $K$ denote it and consider the infinitely many prefixesFor any $i\ne j$, append the word $z_i=(bc{)}^i$. Then $u_i{z}_i\in K$, whereas $u_j{z}_i\notin K$: the latter word has $j$ occurrences of $a$ and $i$ occurrences of $c$, and every word of $K$ has equal numbers of those two symbols.

Thus $u_i$ and $u_j$ are not Myhill-Nerode equivalent. There are infinitely many Myhill-Nerode equivalence classes, so the Myhill-Nerode theorem rules out a finite-state automaton recognizing $K$. Equivalently, if two such prefixes left a deterministic finite automaton in the same automaton state, appending $z_i$ could not distinguish their acceptance, giving the same contradiction.