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) {wn∣w∈{a,b}∗,n⩾2}\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:={wabn∣w∈{a,b}∗,n∈K}∪{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.

Typos? Please submit corrections to this page on GitHub.