Paper 4, Section I, 4H4 \mathrm{H}

Automata and Formal Languages
Part II, 2019

(a) Which of the following are regular languages? Justify your answers.

(i) {wnw{a,b},n2}\left\{w^{n} \mid w \in\{a, b\}^{*}, n \geqslant 2\right\}.

(ii) {w{a,b,c}w\left\{w \in\{a, b, c\}^{*} \mid w\right. contains an odd number of bb 's and an even number of cc 's }\}.

(iii) {w{0,1}w\left\{w \in\{0,1\}^{*} \mid w\right. contains no more than 7 consecutive 0 's }\}.

(b) Consider the language LL over alphabet {a,b}\{a, b\} defined via

L:={wabnw{a,b},nK}{b}L:=\left\{w a b^{n} \mid w \in\{a, b\}^{*}, n \in \mathbb{K}\right\} \cup\{b\}^{*}

Show that LL satisfies the pumping lemma for regular languages but is not a regular language itself.