Automata And Formal Languages

2021

• Paper 1, Section I, F

  Automata and Formal Languages | Part II, 2021

  Let $f_{n, k}$ be the partial function on $k$ variables that is computed by the $n$th machine (or the empty function if $n$ does not encode a machine).

  Define the halting set $\mathbb{K}$.

  Given $A, B \subseteq \mathbb{N}$, what is a many-one reduction $A \leqslant_{m} B$ of $A$ to $B$ ?

  State the $s-m-n$ theorem and use it to show that a subset $X$ of $\mathbb{N}$ is recursively enumerable if and only if $X \leqslant_{m} \mathbb{K}$.

  Give an example of a set $S \subseteq \mathbb{N}$ with $\mathbb{K} \leqslant_{m} S$ but $\mathbb{K} \neq S$.

  [You may assume that $\mathbb{K}$ is recursively enumerable and that $0 \notin \mathbb{K}$.]

  comment

• Paper 1, Section II, F

  Automata and Formal Languages | Part II, 2021

  For $k \geqslant 1$ give the definition of a partial recursive function $f: \mathbb{N}^{k} \rightarrow \mathbb{N}$ in terms of basic functions, composition, recursion and minimisation.

  Show that the following partial functions from $\mathbb{N}$ to $\mathbb{N}$ are partial recursive: (i) $s(n)= \begin{cases}1 & n=0 \\ 0 & n \geqslant 1\end{cases}$ (ii) $r(n)= \begin{cases}1 & n \text { odd } \\ 0 & n \text { even } \text {, }\end{cases}$ (iii) $p(n)=\left\{\begin{array}{l}\text { undefined if } n \text { is odd } \\ 0 \text { if } n \text { is even }\end{array}\right.$

  Which of these can be defined without using minimisation?

  What is the class of functions $f: \mathbb{N}^{k} \rightarrow \mathbb{N}$ that can be defined using only basic functions and composition? [Hint: See which functions you can obtain and then show that these form a class that is closed with respect to the above.]

  Show directly that every function in this class is computable.

  comment

• Paper 2, Section I, F

  Automata and Formal Languages | Part II, 2021

  Assuming the definition of a deterministic finite-state automaton (DFA) $D=$ $\left(Q, \Sigma, \delta, q_{0}, F\right)$, what is the extended transition function $\hat{\delta}$ for $D$ ? Also assuming the definition of a nondeterministic finite-state automaton (NFA) $N$, what is $\hat{\delta}$ in this case?

  Define the languages accepted by $D$ and $N$, respectively, in terms of $\hat{\delta}$.

  Given an NFA $N$ as above, describe the subset construction and show that the resulting DFA $\bar{N}$ accepts the same language as $N$. If $N$ has one accept state then how many does $\bar{N}$ have?

  comment

• Paper 3, Section I, F

  Automata and Formal Languages | Part II, 2021

  Define a regular expression $R$ and explain how this gives rise to a language $\mathcal{L}(R)$.

  Define a deterministic finite-state automaton $D$ and the language $\mathcal{L}(D)$ that it accepts.

  State the relationship between languages obtained from regular expressions and languages accepted by deterministic finite-state automata.

  Let $L$ and $M$ be regular languages. Is $L \cup M$ always regular? What about $L \cap M$ ?

  Now suppose that $L_{1}, L_{2}, \ldots$ are regular languages. Is the countable union $\bigcup L_{i}$ always regular? What about the countable intersection $\bigcap L_{i}$ ?

  comment

• Paper 3, Section II, $12 F$

  Automata and Formal Languages | Part II, 2021

  Suppose that $G$ is a context-free grammar without $\epsilon$-productions. Given a derivation of some word $w$ in the language $L$ of $G$, describe a parse tree for this derivation.

  State and prove the pumping lemma for $L$. How would your proof differ if you did not assume that $G$ was in Chomsky normal form, but merely that $G$ has no $\epsilon$ - or unit productions?

  For the alphabet $\Sigma=\{a, b\}$ of terminal symbols, state whether the following languages over $\Sigma$ are context free, giving reasons for your answer. (i) $\left\{a^{i} b^{i} a^{i} \mid i \geqslant 0\right\}$, (ii) $\left\{a^{i} b^{j} \mid i \geqslant j \geqslant 0\right\}$, (iii) $\left\{w a b w \mid w \in\{a, b\}^{*}\right\}$.

  comment

• Paper 4, Section I, $4 \mathrm{~F}$

  Automata and Formal Languages | Part II, 2021

  State the pumping lemma for regular languages.

  Which of the following languages over the alphabet $\{0,1\}$ are regular?

  (i) $\left\{0^{i} 1^{i} 01 \mid i \geqslant 0\right\}$.

  (ii) $\left\{w \bar{w} \mid w \in\{0,1\}^{*}\right\}$ where $\bar{w}$ is the reverse of the word $w$.

  (iii) $\left\{w \in\{0,1\}^{*} \mid w\right.$ does not contain the subwords 01 or 10$\}$.

  comment

2020

• Paper 1, Section I, $4 \mathbf{F}$

  Automata and Formal Languages | Part II, 2020

  Define an alphabet $\Sigma$, a word over $\Sigma$ and a language over $\Sigma$.

  What is a regular expression $R$ and how does this give rise to a language $\mathcal{L}(R) ?$

  Given any alphabet $\Sigma$, show that there exist languages $L$ over $\Sigma$ which are not equal to $\mathcal{L}(R)$ for any regular expression $R$. [You are not required to exhibit a specific $L$.]

  comment

• Paper 1, Section II, F

  Automata and Formal Languages | Part II, 2020

  (a) Define a register machine, a sequence of instructions for a register machine and a partial computable function. How do we encode a register machine?

  (b) What is a partial recursive function? Show that a partial computable function is partial recursive. [You may assume that for a given machine with a given number of inputs, the function outputting its state in terms of the inputs and the time $t$ is recursive.]

  (c) (i) Let $g: \mathbb{N} \rightarrow \mathbb{N}$ be the partial function defined as follows: if $n$ codes a register machine and the ensuing partial function $f_{n, 1}$ is defined at $n$, set $g(n)=f_{n, 1}(n)+1$. Otherwise set $g(n)=0$. Is $g$ a partial computable function?

  (ii) Let $h: \mathbb{N} \rightarrow \mathbb{N}$ be the partial function defined as follows: if $n$ codes a register machine and the ensuing partial function $f_{n, 1}$ is defined at $n$, set $h(n)=f_{n, 1}(n)+1$. Otherwise, set $h(n)=0$ if $n$ is odd and let $h(n)$ be undefined if $n$ is even. Is $h$ a partial computable function?

  comment

• Paper 2, Section I, F

  Automata and Formal Languages | Part II, 2020

  Assuming the definition of a partial recursive function from $\mathbb{N}$ to $\mathbb{N}$, what is a recursive subset of $\mathbb{N}$ ? What is a recursively enumerable subset of $\mathbb{N}$ ?

  Show that a subset $E \subseteq \mathbb{N}$ is recursive if and only if $E$ and $\mathbb{N} \backslash E$ are recursively enumerable.

  Are the following subsets of $\mathbb{N}$ recursive?

  (i) $\mathbb{K}:=\left\{n \mid n\right.$ codes a program and $f_{n, 1}(n)$ halts at some stage $\}$.

  (ii) $\mathbb{K}_{100}:=\left\{n \mid n\right.$ codes a program and $f_{n, 1}(n)$ halts within 100 steps $\}$.

  comment

• Paper 3, Section I, F

  Automata and Formal Languages | Part II, 2020

  Define a context-free grammar $G$, a sentence of $G$ and the language $\mathcal{L}(G)$ generated by $G$.

  For the alphabet $\Sigma=\{a, b\}$, which of the following languages over $\Sigma$ are contextfree? (i) $\left\{a^{2 m} b^{2 m} \mid m \geqslant 0\right\}$,

  (ii) $\left\{a^{m^{2}} b^{m^{2}} \mid m \geqslant 0\right\}$.

  [You may assume standard results without proof if clearly stated.]

  comment

• Paper 3, Section II, F

  Automata and Formal Languages | Part II, 2020

  Give the definition of a deterministic finite state automaton and of a regular language.

  State and prove the pumping lemma for regular languages.

  Let $S=\left\{2^{n} \mid n=0,1,2, \ldots\right\}$ be the subset of $\mathbb{N}$ consisting of the powers of 2 .

  If we write the elements of $S$ in base 2 (with no preceding zeros), is $S$ a regular language over $\{0,1\}$ ?

  Now suppose we write the elements of $S$ in base 10 (again with no preceding zeros). Show that $S$ is not a regular language over $\{0,1,2,3,4,5,6,7,8,9\}$. [Hint: Give a proof by contradiction; use the above lemma to obtain a sequence $a_{1}, a_{2}, \ldots$ of powers of 2, then consider $a_{i+1}-10^{d} a_{i}$ for $i=1,2,3, \ldots$ and a suitable fixed d.]

  comment

• Paper 4, Section I, $4 F$

  Automata and Formal Languages | Part II, 2020

  Define what it means for a context-free grammar (CFG) to be in Chomsky normal form $(\mathrm{CNF})$.

  Describe without proof each stage in the process of converting a CFG $G=$ $(N, \Sigma, P, S)$ into an equivalent CFG $\bar{G}$ which is in CNF. For each of these stages, when are the nonterminals $N$ left unchanged? What about the terminals $\Sigma$ and the generated language $\mathcal{L}(G)$ ?

  Give an example of a CFG $G$ whose generated language $\mathcal{L}(G)$ is infinite and equal to $\mathcal{L}(\bar{G})$.

  comment

2019

• Paper 1, Section I, H

  Automata and Formal Languages | Part II, 2019

  (a) State the pumping lemma for context-free languages (CFLs).

  (b) Which of the following are CFLs? Justify your answers.

  (i) $\left\{w w^{R} \mid w \in\{a, b\}^{*}\right\}$, where $w^{R}$ is the reverse of the word $w$.

  (ii) $\left\{0^{p} 1^{p} \mid p\right.$ is a prime $\}$.

  (iii) $\left\{a^{m} b^{n} c^{k} d^{l} \mid 3 m=4 l\right.$ and $\left.2 n=5 k\right\}$.

  (c) Let $L$ and $M$ be CFLs. Show that the concatenation $L M$ is also a CFL.

  comment

• Paper 1, Section II, H

  Automata and Formal Languages | Part II, 2019

  Let $D=\left(Q, \Sigma, \delta, q_{0}, F\right)$ be a deterministic finite-state automaton (DFA). Define what it means for two states of $D$ to be equivalent. Define the minimal DFA $D / \sim$ for $D$.

  Let $D$ be a DFA with no inaccessible states, and suppose that $A$ is another DFA on the same alphabet as $D$ and for which $\mathcal{L}(D)=\mathcal{L}(A)$. Show that $A$ has at least as many states as $D / \sim$. [You may use results from the course as long as you state them clearly.]

  Construct a minimal DFA (that is, one with the smallest possible number of states) over the alphabet $\{0,1\}$ which accepts precisely the set of binary numbers which are multiples of 7. You may have leading zeros in your inputs (e.g.: 00101). Prove that your DFA is minimal by finding a distinguishing word for each pair of states.

  comment

• Paper 2, Section I, H

  Automata and Formal Languages | Part II, 2019

  (a) Define a recursive set and a recursively enumerable (r.e.) set. Prove that $E \subseteq \mathbb{N}_{0}$ is recursive if and only if both $E$ and $\mathbb{N}_{0} \backslash E$ are r.e. sets.

  (b) Let $E=\left\{f_{n, k}\left(m_{1}, \ldots, m_{k}\right) \mid\left(m_{1}, \ldots, m_{k}\right) \in \mathbb{N}_{0}^{k}\right\}$ for some fixed $k \geqslant 1$ and some fixed register machine code $n$. Show that $E=\left\{m \in \mathbb{N}_{0} \mid f_{j, 1}(m) \downarrow\right\}$ for some fixed register machine code $j$. Hence show that $E$ is an r.e. set.

  (c) Show that the function $f: \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}$ defined below is primitive recursive.

  $$f(n)= \begin{cases}n-1 & \text { if } n>0 \\ 0 & \text { if } n=0\end{cases}$$

  [Any use of Church's thesis in your answers should be explicitly stated. In this question $\mathbb{N}_{0}$ denotes the set of non-negative integers.]

  comment

• Paper 3, Section I, $4 \mathrm{H}$

  Automata and Formal Languages | Part II, 2019

  (a) Define what it means for a context-free grammar (CFG) to be in Chomsky normal form (CNF). Can a CFG in CNF ever define a language containing $\epsilon$ ? If $G_{\text {Chom }}$ denotes the result of converting an arbitrary CFG $G$ into one in CNF, state the relationship between $\mathcal{L}(G)$ and $\mathcal{L}\left(G_{\text {Chom }}\right)$.

  (b) Let $G$ be a CFG in CNF. Give an algorithm that, on input of any word $v$ on the terminals of $G$, decides if $v \in \mathcal{L}(G)$ or not. Explain why your algorithm works.

  (c) Convert the following CFG $G$ into a grammar in CNF:

  $$\begin{aligned} S \rightarrow & S b b|a S| T \\ & T \rightarrow c c \end{aligned}$$

  Does $\mathcal{L}(G)=\mathcal{L}\left(G_{\text {Chom }}\right)$ in this case? Justify your answer.

  comment

• Paper 3, Section II, 12H

  Automata and Formal Languages | Part II, 2019

  (a) State the $s-m-n$ theorem and the recursion theorem.

  (b) State and prove Rice's theorem.

  (c) Show that if $g: \mathbb{N}_{0}^{2} \rightarrow \mathbb{N}_{0}$ is partial recursive, then there is some $e \in \mathbb{N}_{0}$ such that

  $$f_{e, 1}(y)=g(e, y) \quad \forall y \in \mathbb{N}_{0}$$

  (d) Show there exists some $m \in \mathbb{N}_{0}$ such that $W_{m}$ has exactly $m^{2}$ elements.

  (e) Given $n \in \mathbb{N}_{0}$, is it possible to compute whether or not the number of elements of $W_{n}$ is a (finite) perfect square? Justify your answer.

  [In this question $\mathbb{N}_{0}$ denotes the set of non-negative integers. Any use of Church's thesis in your answers should be explicitly stated.]

  comment

• Paper 4, Section I, $4 \mathrm{H}$

  Automata and Formal Languages | Part II, 2019

  (a) Which of the following are regular languages? Justify your answers.

  (i) $\left\{w^{n} \mid w \in\{a, b\}^{*}, n \geqslant 2\right\}$.

  (ii) $\left\{w \in\{a, b, c\}^{*} \mid w\right.$ contains an odd number of $b$ 's and an even number of $c$ 's $\}$.

  (iii) $\left\{w \in\{0,1\}^{*} \mid w\right.$ contains no more than 7 consecutive 0 's $\}$.

  (b) Consider the language $L$ over alphabet $\{a, b\}$ defined via

  $$L:=\left\{w a b^{n} \mid w \in\{a, b\}^{*}, n \in \mathbb{K}\right\} \cup\{b\}^{*}$$

  Show that $L$ satisfies the pumping lemma for regular languages but is not a regular language itself.

  comment

2018

• Paper 1, Section I, G

  Automata and Formal Languages | Part II, 2018

  (a) State the pumping lemma for context-free languages (CFLs).

  (b) Which of the following are CFLs? Justify your answers.

  (i) $\left\{w w \mid w \in\{a, b, c\}^{*}\right\}$

  (ii) $\left\{a^{m} b^{n} c^{k} d^{l} \mid 3 m=4 n\right.$ and $\left.2 k=5 l\right\}$

  (iii) $\left\{a^{3^{n}} \mid n \geqslant 0\right\}$

  (c) Let $L$ be a CFL. Show that $L^{*}$ is also a CFL.

  comment

• Paper 1, Section II, G

  Automata and Formal Languages | Part II, 2018

  (a) Define the halting set $\mathbb{K}$. Prove that $\mathbb{K}$ is recursively enumerable, but not recursive.

  (b) Given $A, B \subseteq \mathbb{N}$, define a many-one reduction of $A$ to $B$. Show that if $B$ is recursively enumerable and $A \leqslant_{m} B$, then $A$ is also recursively enumerable.

  (c) Show that each of the functions $f(n)=2 n$ and $g(n)=2 n+1$ are both partial recursive and total, by building them up as partial recursive functions.

  (d) Let $X, Y \subseteq \mathbb{N}$. We define the set $X \oplus Y$ via

  $$X \oplus Y:=\{2 x \mid x \in X\} \cup\{2 y+1 \mid y \in Y\}$$

  (i) Show that both $X \leqslant_{m} X \oplus Y$ and $Y \leqslant_{m} X \oplus Y$.

  (ii) Using the above, or otherwise, give an explicit example of a subset $C$ of $\mathbb{N}$ for which neither $C$ nor $\mathbb{N} \backslash C$ are recursively enumerable.

  (iii) For every $Z \subseteq \mathbb{N}$, show that if $X \leqslant_{m} Z$ and $Y \leqslant_{m} Z$ then $X \oplus Y \leqslant_{m} Z$.

  [Note that we define $\mathbb{N}=\{0,1, \ldots\}$. Any use of Church's thesis in your answers should be explicitly stated.]

  comment

• Paper 2, Section I, G

  Automata and Formal Languages | Part II, 2018

  (a) Let $E=\left(Q_{E}, \Sigma, \delta_{E}, q_{0}, F_{E}\right)$ be a nondeterministic finite-state automaton with $\epsilon$-transitions $(\epsilon$-NFA). Define the deterministic finite-state automaton (DFA) $D=\left(Q_{D}, \Sigma, \delta_{D}, q_{D}, F_{D}\right)$ obtained from $E$ via the subset construction with $\epsilon$-transitions.

  (b) Let $E$ and $D$ be as above. By inducting on lengths of words, prove that

  $$\hat{\delta}_{E}\left(q_{0}, w\right)=\hat{\delta}_{D}\left(q_{D}, w\right) \text { for all } w \in \Sigma^{*}$$

  (c) Deduce that $\mathcal{L}(D)=\mathcal{L}(E)$.

  comment

• Paper 3, Section I, G

  Automata and Formal Languages | Part II, 2018

  (a) Define what it means for a context-free grammar (CFG) to be in Chomsky normal form ( $\mathrm{CNF})$.

  (b) Give an algorithm for converting a CFG $G$ into a corresponding CFG $G_{\text {Chom }}$ in CNF satisfying $\mathcal{L}\left(G_{\text {Chom }}\right)=\mathcal{L}(G)-\{\epsilon\}$. [You need only outline the steps, without proof.]

  (c) Convert the following $\mathrm{CFG}\ G$ :

  $$S \rightarrow A S c \mid B, \quad A \rightarrow a, \quad B \rightarrow b$$

  into a grammar in CNF.

  comment

• Paper 3, Section II, G

  Automata and Formal Languages | Part II, 2018

  (a) State and prove the pumping lemma for regular languages.

  (b) Let $D$ be a minimal deterministic finite-state automaton whose language $\mathcal{L}(D)$ is finite. Let $\Gamma_{D}$ be the transition diagram of $D$, and suppose there exists a non-empty closed path $\gamma$ in $\Gamma_{D}$ starting and ending at state $p$.

  (i) Show that there is no path in $\Gamma_{D}$ from $p$ to any accept state of $D$.

  (ii) Show that there is no path in $\Gamma_{D}$ from $p$ to any other state of $D$.

  comment

• Paper 4, Section I, 4G

  Automata and Formal Languages | Part II, 2018

  (a) State the $s-m-n$ theorem, the recursion theorem, and Rice's theorem.

  (b) Show that if $g: \mathbb{N}^{2} \rightarrow \mathbb{N}$ is partial recursive, then there is some $e \in \mathbb{N}$ such that

  $$f_{e, 1}(y)=g(e, y) \quad \forall y \in \mathbb{N}$$

  (c) By considering the partial function $g: \mathbb{N}^{2} \rightarrow \mathbb{N}$ given by

  $$g(x, y)= \begin{cases}0 & \text { if } y<x \\ \uparrow & \text { otherwise }\end{cases}$$

  show there exists some $m \in \mathbb{N}$ such that $W_{m}$ has exactly $m$ elements.

  (d) Given $n \in \mathbb{N}$, is it possible to compute whether or not $W_{n}$ has exactly 9 elements? Justify your answer.

  [Note that we define $\mathbb{N}=\{0,1, \ldots\}$. Any use of Church's thesis in your answers should be explicitly stated.]

  comment

2017

• Paper 1, Section I, $4 \mathrm{H}$

  Automata and Formal Languages | Part II, 2017

  (a) Prove that every regular language is also a context-free language (CFL).

  (b) Show that, for any fixed $n>0$, the set of regular expressions over the alphabet $\left\{a_{1}, \ldots, a_{n}\right\}$ is a CFL, but not a regular language.

  comment

• Paper 1, Section II, $11 H$

  Automata and Formal Languages | Part II, 2017

  (a) Give an encoding to integers of all deterministic finite-state automata (DFAs). [Here the alphabet of each such DFA is always taken from the set $\{0,1, \ldots\}$, and the states for each such DFA are always taken from the set $\left.\left\{q_{0}, q_{1}, \ldots\right\} .\right]$

  (b) Show that the set of codes for which the corresponding DFA $D_{n}$ accepts a finite language is recursive. Moreover, if the language $\mathcal{L}\left(D_{n}\right)$ is finite, show that we can compute its size $\left|\mathcal{L}\left(D_{n}\right)\right|$ from $n$.

  comment

• Paper 2, Section I, $4 \mathrm{H}$

  Automata and Formal Languages | Part II, 2017

  (a) Give explicit examples, with justification, of a language over some finite alphabet $\Sigma$ which is:

  (i) context-free, but not regular;

  (ii) recursive, but not context-free.

  (b) Give explicit examples, with justification, of a subset of $\mathbb{N}$ which is:

  (i) recursively enumerable, but not recursive;

  (ii) neither recursively enumerable, nor having recursively enumerable complement in $\mathbb{N}$.

  comment

• Paper 3, Section I, 4H

  Automata and Formal Languages | Part II, 2017

  (a) Define what it means for a context-free grammar (CFG) to be in Chomsky normal form (CNF). Give an example, with justification, of a context-free language (CFL) which is not defined by any CFG in CNF.

  (b) Show that the intersection of two CFLs need not be a CFL.

  (c) Let $L$ be a CFL over an alphabet $\Sigma$. Show that $\Sigma^{*} \backslash L$ need not be a CFL.

  comment

• Paper 3, Section II, $11 \mathrm{H}$ Automata and formal languages

  Automata and Formal Languages | Part II, 2017

  (a) Given $A, B \subseteq \mathbb{N}$, define a many-one reduction of $A$ to $B$. Show that if $B$ is recursively enumerable (r.e.) and $A \leqslant_{m} B$ then $A$ is also recursively enumerable.

  (b) State the $s-m-n$ theorem, and use it to prove that a set $X \subseteq \mathbb{N}$ is r.e. if and only if $X \leqslant_{m} \mathbb{K}$.

  (c) Consider the sets of integers $P, Q \subseteq \mathbb{N}$ defined via

  $$\begin{aligned} &P:=\left\{n \in \mathbb{N} \mid n \text { codes a program and } W_{n} \text { is finite }\right\} \\ &Q:=\left\{n \in \mathbb{N} \mid n \text { codes a program and } W_{n} \text { is recursive }\right\} \end{aligned}$$

  Show that $P \leqslant \leqslant_{m} Q$.

  comment

• Paper 4, Section I, $4 \mathrm{H}$

  Automata and Formal Languages | Part II, 2017

  (a) Describe the process for converting a deterministic finite-state automaton $D$ into a regular expression $R$ defining the same language, $\mathcal{L}(D)=\mathcal{L}(R)$. [You need only outline the steps, without proof, but you should clearly define all terminology you introduce.]

  (b) Consider the language $L$ over the alphabet $\{0,1\}$ defined via

  $$L:=\left\{w 01^{n} \mid w \in\{0,1\}^{*}, n \in \mathbb{K}\right\} \cup\{1\}^{*} .$$

  Show that $L$ satisfies the pumping lemma for regular languages but is not a regular language itself.

  comment

2016

• Paper 1, Section I, $4 \mathrm{~F}$

  Automata and Formal Languages | Part II, 2016

  State the pumping lemma for context-free languages (CFLs). Which of the following are CFLs? Justify your answers.

  (i) $\left\{a^{2 n} b^{3 n} \mid n \geqslant 3\right\}$.

  (ii) $\left\{a^{2 n} b^{3 n} c^{5 n} \mid n \geqslant 0\right\}$.

  (iii) $\left\{a^{p} \mid p\right.$ is a prime $\}$.

  Let $L, M$ be CFLs. Show that $L \cup M$ is also a CFL.

  comment

• Paper 1, Section II, F

  Automata and Formal Languages | Part II, 2016

  (a) Define a recursive set and a recursively enumerable (r.e.) set. Prove that $E \subseteq \mathbb{N}$ is recursive if and only if both $E$ and $\mathbb{N} \backslash E$ are r.e.

  (b) Define the halting set $\mathbb{K}$. Prove that $\mathbb{K}$ is r.e. but not recursive.

  (c) Let $E_{1}, E_{2}, \ldots, E_{n}$ be r.e. sets. Prove that $\bigcup_{i=1}^{n} E_{i}$ and $\bigcap_{i=1}^{n} E_{i}$ are r.e. Show by an example that the union of infinitely many r.e. sets need not be r.e.

  (d) Let $E$ be a recursive set and $f: \mathbb{N} \rightarrow \mathbb{N}$ a (total) recursive function. Prove that the set $\{f(n) \mid n \in E\}$ is r.e. Is it necessarily recursive? Justify your answer.

  [Any use of Church's thesis in your answer should be explicitly stated.]

  comment

• Paper 2, Section $\mathbf{I}$, $4 F$

  Automata and Formal Languages | Part II, 2016

  (a) Which of the following are regular languages? Justify your answers.

  (i) $\left\{w \in\{a, b\}^{*} \mid w\right.$ is a nonempty string of alternating $a$ 's and $b$ 's $\}$.

  (ii) $\left\{w a b w \mid w \in\{a, b\}^{*}\right\}$.

  (b) Write down a nondeterministic finite-state automaton with $\epsilon$-transitions which accepts the language given by the regular expression $(\mathbf{a}+\mathbf{b})^{*}(\mathbf{b} \mathbf{b}+\mathbf{a}) \mathbf{b}$. Describe in words what this language is.

  (c) Is the following language regular? Justify your answer.

  $$\left\{w \in\{a, b\}^{*} \mid w \text { does not end in } a b \text { or } b b b\right\}$$

  comment

• Paper 3, Section I, $4 F$

  Automata and Formal Languages | Part II, 2016

  (a) Define what it means for a context-free grammar (CFG) to be in Chomsky normal form (CNF). Can a CFG in CNF ever define a language containing $\epsilon$ ? If $G_{\text {Chom }}$ denotes the result of converting an arbitrary CFG $G$ into one in CNF, state the relationship between $\mathcal{L}(G)$ and $\mathcal{L}\left(G_{\text {Chom }}\right)$.

  (b) Let $G$ be a CFG in CNF, and let $w \in \mathcal{L}(G)$ be a word of length $|w|=n>0$. Show that every derivation of $w$ in $G$ requires precisely $2 n-1$ steps. Using this, give an algorithm that, on input of any word $v$ on the terminals of $G$, decides if $v \in \mathcal{L}(G)$ or not.

  (c) Convert the following CFG $G$ into a grammar in CNF:

  $$S \rightarrow a S b|S S| \epsilon$$

  Does $\mathcal{L}(G)=\mathcal{L}\left(G_{\text {Chom }}\right)$ in this case? Justify your answer.

  comment

• Paper 3, Section II, F

  Automata and Formal Languages | Part II, 2016

  (a) Let $D=\left(Q, \Sigma, \delta, q_{0}, F\right)$ be a deterministic finite-state automaton. Define the extended transition function $\hat{\delta}: Q \times \Sigma^{*} \rightarrow Q$, and the language accepted by $D$, denoted $\mathcal{L}(D)$. Let $u, v \in \Sigma^{*}$, and $p \in Q$. Prove that $\hat{\delta}(p, u v)=\hat{\delta}(\hat{\delta}(p, u), v)$.

  (b) Let $\sigma_{1}, \sigma_{2}, \ldots, \sigma_{k} \in \Sigma$ where $k \geqslant|Q|$, and let $p \in Q$.

  (i) Show that there exist $0 \leqslant i<j \leqslant k$ such that $\hat{\delta}\left(p, \sigma_{1} \cdots \sigma_{i}\right)=\hat{\delta}\left(p, \sigma_{1} \cdots \sigma_{j}\right)$, where we interpret $\sigma_{1} \cdots \sigma_{i}$ as $\epsilon$ if $i=0$.

  (ii) Show that $\hat{\delta}\left(p, \sigma_{1} \cdots \sigma_{i} \sigma_{j+1} \cdots \sigma_{k}\right)=\hat{\delta}\left(p, \sigma_{1} \cdots \sigma_{k}\right)$.

  (iii) Show that $\hat{\delta}\left(p, \sigma_{1} \cdots \sigma_{i}\left(\sigma_{i+1} \cdots \sigma_{j}\right)^{t} \sigma_{j+1} \cdots \sigma_{k}\right)=\hat{\delta}\left(p, \sigma_{1} \cdots \sigma_{k}\right)$ for all $t \geqslant 1$.

  (c) Prove the following version of the pumping lemma. Suppose $w \in \mathcal{L}(D)$, with $|w| \geqslant|Q|$. Then $w$ can be broken up into three words $w=x y z$ such that $y \neq \epsilon,|x y| \leqslant|Q|$, and for all $t \geqslant 0$, the word $x y^{t} z$ is also in $\mathcal{L}(D)$.

  (d) Hence show that

  (i) if $\mathcal{L}(D)$ contains a word of length at least $|Q|$, then it contains infinitely many words;

  (ii) if $\mathcal{L}(D) \neq \emptyset$, then it contains a word of length less than $|Q|$;

  (iii) if $\mathcal{L}(D)$ contains all words in $\Sigma^{*}$ of length less than $|Q|$, then $\mathcal{L}(D)=\Sigma^{*}$.

  comment

• Paper 4, Section I, $4 \mathrm{~F}$

  Automata and Formal Languages | Part II, 2016

  (a) Construct a register machine to compute the function $f(m, n):=m+n$. State the relationship between partial recursive functions and partial computable functions. Show that the function $g(m, n):=m n$ is partial recursive.

  (b) State Rice's theorem. Show that the set $A:=\left\{n \in \mathbb{N}|| W_{n} \mid>7\right\}$ is recursively enumerable but not recursive.

  comment