 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/models-of-computation/3/b/ii/solution

The formal language is not a regular language. Let

K

denote it and consider the infinitely many prefixes

u_{i} = (ab)^{i}, i \geq 0.

For any

i \neq = j

, append the word

z_{i} = (b c)^{i}

. Then

u_{i} z_{i} \in K

, whereas

u_{j} z_{i} \in / 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}

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.

K is not regular .

 New to topics? Read the docs here!