Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 4 / 4F (Automata and Formal Languages)

The pumping lemma for regular languages says that sufficiently long accepted words split as $xyz$ with $|xy|\le P$, $|y|>0$, and $x{y}^{k}z$ accepted for all $k\ge 0$. Applying it to $0^P{1}^{P}01$ pumps only zeros, so language (i) is not regular.

This language is not regular. Intersecting with the regular language $0^{\ast }110^{\ast }$ isolates strings whose two zero blocks must have equal length; the pumping lemma then gives a contradiction.

A word containing neither $01$ nor $10$ cannot change symbol. The language is therefore $0^{\ast }\cup 1^{\ast }$, hence is regular.