Paper 4, Section I, 4 F4 \mathrm{~F}

Automata and Formal Languages
Part II, 2021

State the pumping lemma for regular languages.

Which of the following languages over the alphabet {0,1}\{0,1\} are regular?

(i) {0i1i01i0}\left\{0^{i} 1^{i} 01 \mid i \geqslant 0\right\}.

(ii) {wwˉw{0,1}}\left\{w \bar{w} \mid w \in\{0,1\}^{*}\right\} where wˉ\bar{w} is the reverse of the word ww.

(iii) {w{0,1}w\left\{w \in\{0,1\}^{*} \mid w\right. does not contain the subwords 01 or 10}\}.