Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Calculus, linear algebra, discrete mathematics, logic and proof, and models of computation / 9 / b

Every finite formal language is a regular language. A single string $a_1\cdots a_k$ is described by the regular expression formed by concatenating its symbols; the empty string is described by $\epsilon$. A finite union of these regular expressions describes any specified finite collection of strings. The empty collection is described by $\varnothing$. ThusEquivalently, a deterministic finite automaton can remember which prefix of one of the finitely many accepted strings has been read, moving to a rejecting dead state when no such prefix remains possible.

These strings are the even-length palindromes $u{u}^R$. Suppose this were a regular language, and let $p$ be its length from the pumping lemma for regular languages. The stringbelongs to the formal language, with $u=0^{p}1$. In any allowed decomposition $w=abc$, where $|ab|\le p$ and $|b|>0$, the pumped block is $b=0^k$ with $1\le k\le p$. Pumping it away givesThis is not a palindrome: its initial and final runs of zeros have different lengths. Hence it cannot have the form $u{u}^R$, contradicting the pumping lemma for regular languages. Therefore

This is a regular language. A deterministic finite automaton needs only to remember the number of consecutive trailing ones, up to three, and whether a forbidden run of four has already occurred. Use states $q_0,q_1,q_2,q_3,q_{\times }$, start at $q_0$, and accept in $q_0,q_1,q_2,q_3$. Its transition function of a finite automaton is:

Reading a zero resets the trailing count unless rejection has already occurred. A fourth successive one enters the permanent rejecting state $q_{\times }$. Thus the accepted strings are exactly those with no substring $1111$, and

Let $L=\{0^m{1}^n:m,n\ge 0,m\ne n\}$, and suppose it were a regular language. The formal language $B=0^{\ast }{1}^{\ast }$ is a regular language. By closure of regular languages under set difference,would be a regular language. But the pumping lemma for regular languages rules this out: for pumping length $p$, every permitted pumped block in $0^p{1}^p$ consists of $k>0$ zeros, and deleting it produces $0^{p-k}{1}^p$, with unequal counts. This contradiction provesThe closure step can also be realized by a product automaton accepting when the automaton for $B$ accepts and the automaton for $L$ rejects. If the exponents are instead required to be positive, use $B=0^{+}{1}^{+}$; the same argument applies.