Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3

Fix a deterministic, single-tape Turing machine with tape cells indexed by the integers. A precise definition is the tupleHere $Q$ is a nonempty finite set of control states, $\Gamma$ a finite tape alphabet with a designated blank symbol $\square$, $\Sigma \subseteq \Gamma \setminus \{\square \}$ the input alphabet, $q_0\in Q$ the initial control state, and $q_{\mathrm{acc}},q_{\mathrm{rej}}\in Q$ distinct halting control states. The transition function is total on the displayed domain. The Turing machine instruction $\delta (q,a)=(r,b,D)$ means to write $b$ over the scanned $a$, enter control state $r$, and move the head one cell in direction $D$.

A Turing machine configuration is $(q,\tau ,h)$, where $q\in Q$, $h\in \mathbb{Z}$ is the head position, and $\tau :\mathbb{Z}\to \Gamma$ is the tape-content function, equal to $\square$ outside a finite set. Its next-configuration relation isif $\delta (q,\tau (h))=(r,b,D)$, with $d=-1$ for $D=L$ and $d=1$ for $D=R$, andThere is no successor to either halting Turing machine configuration.

For input $w=a_0\cdots a_{n-1}$, the initial Turing machine configuration is $C_0(w)=(q_0,{\tau }_w,0)$, where ${\tau }_w(j)=a_j$ for $0\le j<n$ and is blank elsewhere. In particular, the initial tape for the empty word is entirely blank. The recognized formal language isThe relation ${⊢}_M^{\ast }$ permits any finite number of transitions. An input outside $L(M)$ may reach the rejecting control state or run forever; recognition does not require halting on every input.

The formal language is a regular language. A regular expression for it isThe first Kleene star independently chooses $m$ copies of the word $ab$, and the second independently chooses $n$ copies of $bc$. Their concatenation produces exactly the required words. Either count may be zero, including both counts zero, which gives the empty word. By Kleene theorem, the regular expression establishes regularity.

The formal language is not a regular language. Let $K$ denote it and consider the infinitely many prefixesFor any $i\ne j$, append the word $z_i=(bc{)}^i$. Then $u_i{z}_i\in K$, whereas $u_j{z}_i\notin K$: the latter word has $j$ occurrences of $a$ and $i$ occurrences of $c$, and every word of $K$ has equal numbers of those two symbols.

Thus $u_i$ and $u_j$ are not Myhill-Nerode equivalent. There are infinitely many Myhill-Nerode equivalence classes, so the Myhill-Nerode theorem rules out a finite-state automaton recognizing $K$. Equivalently, if two such prefixes left a deterministic finite automaton in the same automaton state, appending $z_i$ could not distinguish their acceptance, giving the same contradiction.

The formal language is a context-free language. A context-free grammar with start nonterminal symbol $S$ isThe production rule for $A$ nests one $a$ on the left and one $b$ on the right on each recursive use, so $A$ generates exactly $a^m{b}^m$ for $m\ge 0$. Similarly, $B$ generates exactly $b^n{c}^n$ for $n\ge 0$. The start production rule concatenates these words, yieldingConversely, every choice of nonnegative integers $m,n$ is achieved by using the recursive production rules exactly $m,n$ times before their epsilon productions. Hence this context-free grammar generates precisely the required formal language, including all cases where either count is zero.

The formal language is not a context-free language. Suppose otherwise, and let $p\ge 1$ be a pumping length from the pumping lemma for context-free languages. ChooseThis word belongs to the formal language, since its middle exponent is the product of the two outer exponents. The pumping lemma for context-free languages would givewith $u{v}^{i}x{y}^{i}z$ in the formal language for every integer $i\ge 0$.

Let $\alpha ,\beta ,\gamma$ be the respective numbers of $a,b,c$ symbols in the two pumped pieces $v,y$ together. The window $vxy$ cannot contain both an $a$ and a $c$: it would have to contain the entire middle block of length $p^2$, plus at least those two outer symbols, exceeding $p$. HencePump once extra, taking $i=2$. The resulting symbol counts are $p+\alpha$, $p^2+\beta$, and $p+\gamma$. A necessary condition for membership, regardless of whether the block order survives, iswhere $\alpha \gamma =0$ was used.

If $\alpha +\gamma =0$, then $\beta >0$, contradicting that equality. If $\alpha +\gamma \ge 1$, thenagain contradicting it. Thus every permissible decomposition fails at $i=2$. This contradicts the pumping lemma for context-free languages and proves the claim. The obstruction is the multiplicative block-count language: a bounded local change cannot preserve the product constraint.

The problem is decidable. We need exactly one accepted word, even if that word has several accepting runs in the nondeterministic finite automaton.

First convert the input nondeterministic finite automaton to an equivalent deterministic finite automaton $D$ using the subset construction, taking epsilon closure where necessary. In the finite transition directed graph of $D$, test whether an accepting automaton state is reachable from the initial automaton state. This is the standard finite automaton emptiness test. If none is reachable, the recognized formal language is empty, so answer no.

Otherwise retain a graph path to an accepting automaton state and read its labels to obtain one accepted word $w$. If the initial automaton state is accepting, $w$ may be the empty word. Build a complete deterministic finite automaton for the singleton formal language $\{w\}$: it tracks the matching prefix of $w$, accepts only after exactly its full length, and enters a rejecting sink on a mismatch or any extra input symbol.

Complement that complete deterministic finite automaton by exchanging accepting and rejecting automaton states. Form its product with $D$, accepting exactly when the $D$ coordinate accepts and the other coordinate accepts. This product recognizesApply the finite automaton emptiness test again. Answer yes if and only if this difference is empty. The first test guarantees that $w$ belongs to $L(D)$; the second guarantees there is no different accepted word. All constructions have finitely many automaton states and all reachability tests terminate. This gives a singleton-language test for finite automata.

The problem is undecidable. Reduce the halting problem to it. Given a Turing machine $M$ and input word $w$, construct a Turing machine $T$ over $\{a,b,c\}$ with the following behavior on input $x$:

This is an effective construction: $M,w$ are fixed data stored in the description of $T$. Its recognized formal language isTherefore $T$ accepts exactly one input word if and only if $M$ halts on $w$. A supposed decision procedure for the singleton-language problem for Turing machines, applied to the constructed $T$, would decide the halting problem. The standard undecidability of the halting problem excludes that possibility.