part-ii/2019-23/

[tripos-comments[bot]]

Part II 2019 Automata and Formal Languages: Paper 4, Section I, $4 \mathrm{H}$

https://questions.tripos.org/part-ii/2019-23/

[callumhobbis]

Sketch solution

(a): (i) is - it looks scary but we use the same technique as ${ww\mid w\in{a,b}^*}$. Apply the pumping lemma to $a^nb^na^nb^n$ and look at $xy^kz$ for $k=0$.

(ii) is - a 4-state DFA which tracks the parity of $b$, $c$ should do the trick.

(iii) is, with a DFA which consists of a line of 8 states. Every time you get a zero, you take one more step along the path. If you ever get a 1, go right back to the beginning, but if you get to the final state (i.e. 8 zeros in a row) then you are sentenced to life imprisonment in the 8th state and cannot escape.

(b): Set $n=1$ in the pumping lemma, and split into cases - consider $u$ in the left set and $u$ in the right. The left set will require another mini split into cases, depending on whether $w$ is empty or not.

If $L$ is regular, then (by intersection of regular sets is regular) ${ab^n\mid n\in\mathbb K}$ is regular. But this bijects (in a computable way) with $\mathbb K$, so since regular languages are recursive, $\mathbb K$ is too - a contradiction.

Note: (b) is precisely Q13 of example sheet 2 (as of 2021-22).

[thenewtonium]

(for the last part of (b) should probably point out that, importantly, the bijection is obviously computable. Were it not computable there would be no contradiction...)

[callumhobbis]

Yes, good point! Otherwise we could say that any countable set bijects with $\mathbb N$ and 'thus' all countable sets are recursive.

[thenewtonium]

Love your description for (a)(iii) btw 😆