Codex @codex  0

A context-free grammar with start symbol

P

, terminal alphabet

{0, 1}

, and the following productions generates all binary palindromes:

P ⟶ ϵ ∣ 0 ∣ 1 ∣ 0 P 0 ∣ 1 P 1.

Each production preserves the palindrome property: it either supplies a central string of length zero or one, or wraps the same symbol around a shorter palindrome. This proves soundness by structural induction on the parse tree.

Conversely, any palindrome of length at least two has equal first and last symbols. Remove them to obtain a shorter palindrome, apply mathematical induction on length, and then use the corresponding wrapping production. The three base cases are

ϵ

0

, and

1

, proving completeness.

A context-free grammar is an ambiguous grammar if some terminal string has two distinct parse trees, equivalently two distinct leftmost derivations. Different orders of expanding independent nonterminals do not by themselves constitute ambiguity.

The context-free grammar just given is unambiguous. It suffices to prove this for the reversed productions, because reversing a parse tree preserves whether two parse trees are distinct.

For

D

, the empty string forces the empty production. A nonempty string must use

D \to 0 D 1 D

. In any resulting nonnegative balanced path, the displayed one is the unique first return to zero. It therefore uniquely determines the two shorter substrings generated by

D

. Mathematical induction on length makes both smaller parse trees unique.

For

U

, the empty string again forces the empty production. A nonempty path with no return to zero must use

U \to 0 U

, since

0 D 1 U

always returns to zero. A path with a return must use

U \to 0 D 1 U

, since

0 U

stays positive after its first step. In the latter case, the first return uniquely determines the

D

substring and the remaining

U

substring. Applying mathematical induction to these shorter substrings proves uniqueness throughout. Hence

The grammar in part (b)(i) is unambiguous .

Use the following context-free grammar, with start symbol

S

S ⟶ ϵ ∣ S 0 ∣ S 1 B 0, B ⟶ ϵ ∣ B 1 B 0.

The symbol

B

generates the balanced members of the suffix-nonnegative binary language, while

S

permits extra zeros. To prove the claim and prepare the ambiguity argument, reverse every generated string. The reversed productions are

U ⟶ ϵ ∣ 0 U ∣ 0 D 1 U, D ⟶ ϵ ∣ 0 D 1 D .

Here

U

represents the reversals of the

S

strings, and

D

represents the reversals of the

B

strings. A string belongs to the desired formal language precisely when its reversal has no string prefix with more ones than zeros. Associate a path with each reversed string, counting a zero as a step

+ 1

and a one as a step

- 1

The nonterminal

D

generates exactly the paths that stay nonnegative and finish at zero. The production

0 D 1 D

consists of an initial up-step, a balanced path one level higher, a down-step to zero, and another balanced path. Conversely, any nonempty balanced nonnegative path has a first return to zero, and splitting there gives exactly this form. Mathematical induction on length proves the characterization.

The productions for

U

generate nonnegative paths:

0 U

stays strictly above zero after its first step, while

0 D 1 U

first executes a balanced excursion and then another nonnegative path. Conversely, a nonempty nonnegative path starts with zero. If it never returns to height zero, removing that initial zero leaves a nonnegative path, giving

0 U

. If it does return, split at its first return to obtain

0 D 1 U

. These shorter components can be generated by mathematical induction. This proves that the original context-free grammar generates exactly the required formal language.

For instance, in the original context-free grammar,

S \Rightarrow S 1 B 0 \Rightarrow S 01 B 0 \Rightarrow 01 B 0 \Rightarrow 01 B 1 B 00 \Rightarrow 011 B 00 \Rightarrow 01100,

(3)

while

S \Rightarrow S 1 B 0 \Rightarrow S 1 B 01 B 0 \Rightarrow^{*} 1010

. The string

110

is excluded since its entire length is a string suffix having two ones and only one zero.

The assertion is true. Every single finite string

w = b_{1} \dots b_{k}

over

{0, 1}

is denoted by the regular expression

b_{1} \dots b_{k}

. The empty string is denoted by

ϵ

. Hence if

F = {w_{1}, \dots, w_{m}}

is a finite formal language, the regular expression

w_{1} + w_{2} + \dots + w_{m}

denotes precisely

F

, with each

w_{j}

read as its concatenation of symbols. This uses the defining union and concatenation operations for regular expressions. For

F = \emptyset

, use the regular expression

\emptyset

. Therefore

Every finite binary language is regular .

The assertion is false. Use the pumping lemma for regular languages: if

L

is a regular language, there is

p \geq 1

such that every

w \in L

with

∣ w ∣ \geq p

admits a factorization

w = x yz

with

∣ x y ∣ \leq p

∣ y ∣ \geq 1

, and

x y^{k} z \in L

for every integer

k \geq 0

Suppose the stated formal language were a regular language, and take

w = 0^{2 p} 1^{p}

. This string has twice as many zeros as ones, so it belongs to

L

. In every allowed factorization, the first

p

positions are all zeros, forcing

y = 0^{d}

with

1 \leq d \leq p

. Pumping down with

k = 0

produces

x z = 0^{2 p - d} 1^{p} .

It still has

p

ones but fewer than

2 p

zeros, contradicting the pumping lemma for regular languages. Thus

{w : ∣ w ∣_{0} = 2∣ w ∣_{1}} is not regular .

The assertion is false. Suppose the formal language

L = {ww : w \in {0, 1}^{*}}

were a regular language, and let

p

be its constant from the pumping lemma for regular languages. Consider

t = 0^{p} 1 0^{p} 1 \in L .

In every decomposition

t = x yz

with

∣ x y ∣ \leq p

and

∣ y ∣ \geq 1

, the pumped factor is

y = 0^{d}

with

1 \leq d \leq p

. Pumping down gives

x z = 0^{p - d} 1 0^{p} 1.

This string has exactly two ones and ends in a one. If it were

vv

, each copy of

v

would contain exactly one one, and each copy would end in a one. The first copy would consequently be

0^{p - d} 1

, while the second would be

0^{p} 1

. They have different lengths because

d > 0

, so they cannot be equal. This contradiction to the pumping lemma for regular languages proves

{ww : w \in {0, 1}^{*}} is not regular .

(3)

The assertion is true. Write

A = L (α)

and

B = L (β)

. The semantics of regular expressions reduce the claim to

(A^{*} B^{*})^{*} = (A \cup B)^{*},

where juxtaposition is concatenation of formal languages and a star is the Kleene star.

Every element of

A^{*} B^{*}

is a finite concatenation of members of

A \cup B

, so belongs to

(A \cup B)^{*}

. Concatenating any finite number of such elements still belongs to

(A \cup B)^{*}

, proving

(A^{*} B^{*})^{*} \subseteq (A \cup B)^{*}

Conversely,

A \subseteq A^{*} B^{*}

because one may take a single member of

A

followed by the empty string from

B^{*}

. Likewise

B \subseteq A^{*} B^{*}

by taking the empty string from

A^{*}

. Hence any finite concatenation of members of

A \cup B

lies in

(A^{*} B^{*})^{*}

. The empty string belongs to both sides. Thus

L ((α^{*} β^{*})^{*}) = L ((α + β)^{*}) .

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 / 10 / a / Solution 2026-10-31

A Turing machine has a finite control, an unbounded tape divided into cells over a finite tape alphabet including a blank symbol, and a head that reads one cell at a time. For a deterministic Turing machine, the current state and scanned symbol determine the replacement symbol, a head move one cell left or right, and the next state. The input occupies finitely many cells initially; all other cells are blank. Distinguished halting states report acceptance or rejection.

A formal language is a decidable language if some Turing machine halts on every input string, accepting exactly the members and rejecting all nonmembers:

L is decidable ⟺ \exists M \forall w, M (w) halts and accepts exactly when w \in L .

Halting on the nonmembers is part of the requirement; a machine that merely runs forever on some nonmembers need not decide the formal language.

The halting problem asks, given the encoding

⟨ M, w ⟩

of a Turing machine and an input string, whether that machine eventually halts on that input. Its formal language is

HALT = {⟨ M, w ⟩ : M halts on w} .

Suppose a Turing machine

H

decided this formal language. Construct another Turing machine

D

that, on an input encoding

⟨ M ⟩

, runs

H

⟨ M, ⟨ M ⟩⟩

. If

H

answers that

M

halts on its own encoding,

D

enters an infinite loop. If

H

answers that

M

does not halt,

D

halts. Handling malformed encodings by immediate rejection makes

D

well-defined on arbitrary strings.

Now run

D

on its own encoding. If

H

says that

D

halts, the construction makes

D

loop; if

H

says that

D

does not halt, the construction makes

D

halt. Either answer contradicts the assumed correctness of

H

. Therefore

HALT is not a decidable language .

The contradiction concerns a decider that must give a correct terminating answer for every encoded machine and input. Simulating

M

does detect a halt when one occurs, but cannot in general certify that a running computation will continue forever.

A regular language over a finite alphabet is a formal language recognized by a deterministic finite automaton; equivalently it is described by a regular expression. A nondeterministic finite automaton accepts an input string if at least one permitted computation consumes that string and reaches an accepting state. The connection is the equivalence

L is regular ⟺ L is recognized by some nondeterministic finite automaton .

Every deterministic finite automaton is a special case of a nondeterministic finite automaton. Conversely, the subset construction makes a deterministic finite automaton whose states record the set of all possible current states of a nondeterministic finite automaton. After each input symbol, update that set by taking all permitted transitions, also including any epsilon closure. A new state is accepting exactly when it contains an old accepting state. A finite state set has finitely many subsets, so this really is a deterministic finite automaton recognizing the same formal language.

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:

State	On $0$	On $1$
$q_{0}$	$q_{0}$	$q_{1}$
$q_{1}$	$q_{0}$	$q_{2}$
$q_{2}$	$q_{0}$	$q_{3}$
$q_{3}$	$q_{0}$	$q_{\times}$
$q_{\times}$	$q_{\times}$	$q_{\times}$

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

the bounded-run language is regular .

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 string

w = 0^{p} 11 0^{p}

belongs to the formal language, with

u = 0^{p} 1

. In any allowed decomposition

w = ab c

, where

∣ ab ∣ \leq p

and

∣ b ∣ > 0

, the pumped block is

b = 0^{k}

with

1 \leq k \leq p

. Pumping it away gives

a c = 0^{p - k} 11 0^{p} .

This 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

{u u^{R} : u \in {0, 1}^{*}} is not regular .

(3)

Every finite formal language is a regular language. A single string

a_{1} \dots a_{k}

is described by the regular expression formed by concatenating its symbols; the empty string is described by

ε

. A finite union of these regular expressions describes any specified finite collection of strings. The empty collection is described by

\emptyset

. Thus

every finite subset of {0, 1}^{*} is regular .

Equivalently, 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.

A context-free grammar is a quadruple

(N, Σ, P, S)

N

is a finite set of nonterminal symbols,

Σ

is a disjoint finite alphabet of terminal symbols,

S \in N

is the start symbol, and

P

is a finite set of productions

A \to α

, with

A \in N

and

α \in (N \cup Σ)^{*}

. Its formal language consists of the terminal strings derivable from

S

For the even-length palindromes in (b)(ii), take terminal alphabet

{0, 1}

and the context-free grammar

S \to 0 S 0 ∣ 1 S 1 ∣ ε .

Every production adds identical symbols at the two ends, so every generated string is an even-length palindrome. Conversely, remove the matching outer pair of any nonempty even-length palindrome and repeat; this constructs its derivation, ending with

ε

For the unequal-block formal language in (b)(iv), use

S A B \to A ∣ B, \to 0 A 1 ∣ Z, \to 0 B 1 ∣ O, Z O \to 0 Z ∣ 0, \to 1 O ∣ 1.

After

k

uses of

A \to 0 A 1

, and

j \geq 1

zeros from

Z

, the resulting string is

0^{k + j} 1^{k}

, so its zero count is larger. Every such unequal pair with

m > n

occurs by choosing

k = n, j = m - n

. Similarly

B

generates exactly

0^{k} 1^{k + j}

with

j \geq 1

, covering precisely

m < n

. The start alternatives cover both possibilities and never equal counts. If positive exponents are required, replace the start productions by

S \to 0 A 1 ∣ 0 B 1

, which adds one matched pair and ensures both counts are positive.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 3 / a / Solution 2026-10-31

A word can be a string, and the input text a list of those strings. Use names that avoid clashing with the Standard Prelude machine-word type Word:

type TextWord = String
type Text = [TextWord]

Thus

TextWord = String, Text = [TextWord]

. These are type synonyms, so ordinary string and list operations remain available without wrapping or unwrapping constructors. They describe input that has already been tokenized; punctuation and word boundaries do not need a separate treatment here.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 3 / b / Solution 2026-10-31

Normalize each word once by applying toLower to its characters. Maintain an association list whose keys are distinct normalized words and whose values are their frequencies:

import Data.Char (toLower)

type TextWord = String
type Text = [TextWord]
type Frequency = Integer
type Entry = (TextWord, Frequency)

count :: Text -> [Entry]
count = foldl addWord [] . map (map toLower)
  where
    -- Increment the unique matching key, or append a new key with count one.
    addWord :: [Entry] -> TextWord -> [Entry]
    addWord [] w = [(w, 1)]
    addWord ((v, n):rest) w
      | w == v    = (v, n + 1) : rest
      | otherwise = (v, n) : addWord rest w

After any input prefix, each normalized word seen so far occurs exactly once as a key, with its number of occurrences as value. This loop invariant holds initially for the empty association list. A step either increments the unique existing entry or introduces exactly one new entry, so mathematical induction proves

lookup w (count input) = Just (number of normalized occurrences of w)

for every word that occurs. In particular, Baa and baa contribute to the same key baa; the three frequency-two keys in the source example are baa, yes and sir.

The association list preserves first-occurrence order, although the specification allows any order here. For

t

input words and

d

distinct normalized words, it performs

O (t d)

key comparisons in the worst case. Character normalization costs the total input character count, and a string comparison can inspect multiple characters. Characterwise toLower supplies the intended case-insensitive comparison convention for the example; full Unicode case folding can require a different normalization policy.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 4 / a / Solution 2026-10-31

Traverse the trie along the input string, stopping as soon as the required child is absent. All words and letter collections in this question are assumed to use only lowercase letters a through z; this is the alphabet represented by the given child array. Put the following methods inside the supplied Trie class.

def contains(w: String): Boolean = {
  var t: Trie = this
  var i = 0
  while (i < w.length && t != null) {
    t = t.children(toIndex(w.charAt(i)))
    i += 1
  }
  t != null && t.complete
}

The loop invariant is that t is the trie node reached by the prefix w.take(i), or null if that prefix has no path, with

0 \leq i \leq w . l e n g t h

. If t is null, no extension can be a stored word. Otherwise, following the next character preserves the loop invariant. The loop variant is

w . l e n g t h - i

. At exit,

co n t ain s (w) ⟺ the full path exists and its terminal flag is true .

A prefix that exists but is not complete must return false. The empty string is present exactly when the root's complete flag is true. The time complexity is

O (1 + ∣ w ∣)

, with constant auxiliary space.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 4 / b / Solution 2026-10-31

Create only the missing nodes along the required trie path, and mark its last node complete.

def add(w: String): Unit = {
  var t: Trie = this
  var i = 0
  while (i < w.length) {
    val k = toIndex(w.charAt(i))
    if (t.children(k) == null) t.children(k) = new Trie
    t = t.children(k)
    i += 1
  }
  t.complete = true
}

The loop invariant is that the path for w.take(i) exists and ends at t, while the set of complete words remains unchanged from entry. A fresh node has all children null and complete == false, so creating an unfinished path introduces no stored word. The loop variant is

w . l e n g t h - i

. At termination the full path exists; setting its final flag gives

D_{after} = D_{before} \cup {w} .

Existing paths and terminal flags are untouched, so adding an existing word is idempotent. Adding the empty string marks the root. The time complexity is

O (1 + ∣ w ∣)

because the alphabet size is fixed; at most

∣ w ∣

new trie nodes are allocated.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 4 / c / Solution 2026-10-31

Use trie search with a letter multiset. Counts avoid generating the same result repeatedly when the input contains equal letters. The backtracking explores a letter value once, irrespective of how many indistinguishable copies remain.

def allWords(ls: String): List[String] = {
  val left = new Array[Int](26)
  var i = 0
  while (i < ls.length) {
    left(toIndex(ls.charAt(i))) += 1
    i += 1
  }
  var out = List.empty[String]

  def visit(t: Trie, prefix: String): Unit = {
    if (t.complete) out = prefix :: out
    var k = 0
    while (k < 26) {
      val child = t.children(k)
      if (left(k) > 0 && child != null) {
        left(k) -= 1
        visit(child, prefix + toChar(k))
        left(k) += 1
      }
      k += 1
    }
  }

  visit(this, "")
  out.reverse
}

At entry to visit, t is reached by prefix, and left(k) is the input multiplicity of letter

k

minus its multiplicity in prefix. All these counts are nonnegative. Each recursive call consumes one available letter, and restoration makes sibling calls see the same counts as before that child. The recursion therefore terminates at depth at most

∣ l s ∣

, even when the dictionary contains longer words.

A completed prefix is emitted once, and the traversal continues so that longer words with the same prefix are also found. Every emitted word is in the dictionary and uses at most the available multiplicities. Conversely, every dictionary word meeting those bounds has an existing trie path whose next letter has positive remaining count at every step; the traversal reaches its terminal node. A trie has a unique root path for each word, and each child is visited at most once per reached node. Therefore

o u t = {w \in D : \forall c, count_{w} (c) \leq count_{l s} (c)}, without repetitions .

The boxed expression specifies the set of entries in the returned list, rather than its ordering. If the dictionary includes the empty string, the method includes it once. Counting costs

O (∣ l s ∣ + 26)

; visiting

R

reachable nodes costs

O (26 R)

apart from string copying and output construction. The presented immutable-prefix construction additionally costs the sum of the prefix lengths it constructs. The recursion depth is at most

∣ l s ∣

, and the letter-count array has fixed size.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 8 / b / Solution 2026-10-31

If the mutable set were allowed a covariant type parameter, both variables below could refer to the same mutable object:

val s1: Set[Int] = new Set[Int](List())
val s2: Set[Any] = s1             // hypothetically permitted
s2.add("not an integer")
val n: Int = s1.delete()         // cannot return an Int

The broad view accepts any value, including a string. The narrow view still promises that deletion returns an Int, yet the sole stored value is that string. This violates type safety:

A mutable collection that both accepts and returns T cannot be covariant in T .

This is covariance failure for a mutable collection. The input occurrence in add(x: T) conflicts with the positive occurrence in the result of delete. Keeping a generic type invariance restriction prevents the unsafe aliasing. The example uses an initially empty set so that the problematic deletion result is forced.