R_1)]$. \end{quote} Note the longer the program and the more lines it has, the more complex are the update conditions. They have not only to specify which variables change, but also those which keep their values. Such an $U$ can be defined for every register machine. \ownnumnameonly{Example}{Run of a Register Machine} One could code the values of the registers in digits step by step. For example, when all values are bounded by $10$, for computing sum$(3)$, the following sequences would permit to keep track of the configurations at each step: \begin{verbatim} LN: 1 2 3 2 3 2 3 2 3 4 R1: 3 3 3 3 3 3 3 3 3 3 R2: 0 0 0 0 1 1 3 3 6 6 R3: 0 0 1 1 2 2 3 3 4 4 \end{verbatim} So the third column says that after two steps, the register machine is going to do Line 3 and has register values 3,0,1 prior to doing the commands in Line 3. The last column says that the register machine has reached Line 4 and has register values 3,6,4 prior to doing the activity in Line 4 which is to give the output 6 of Register $R_2$ and terminate. \ownsmallpar Now one could code each of these in a decimal number. The digit relating to $10^t$ would have the configurations of the registers and line numbers at the beginning of step $t$ of the computation. Thus the corresponding decimal numbers would be $4323232321$ for LN and $3333333333$ for $R_1$ and $6633110000$ for $R_2$ and $4433221100$ for $R_3$. Note that the updates of a line take effect whenever the next step is executed. \ownsmallpar In the real coding, one would not use $10$ but a prime number $p$. The value of this prime number $p$ just depends on the values the registers take during the computation; the larger these are, the larger $p$ has to be. Now the idea is that the $p$-adic digits for $p^t$ code the values at step $t$ and for $p^{t+1}$ code the values at step $t+1$ so that one can check the update. \ownsmallpar Now one can say that the program Sum$(x)$ computes the value $y$ iff there exist $q,p,LN,R_1,R_2,R_3$ such that $q$ is a power of $p$ and $p$ is a prime and $LN,R_1,R_2,R_3$ code a run with input $x$ and output $y$ in the format given by $p,q$. More precisely, for given $x,y$ there have to exist $p,q,LN,R_1,R_2,R_3$ satisfying the following conditions: \begin{enumerate} \parsep0pt \parskip0pt \itemsep1pt \item $(p,q) \in E$, that is, $p$ is a prime and $q$ is a power of $p$; \item $R_1 = r_1 \cdot p+x$ and $LN = r_{LN} \cdot p+1$ and $p > x+1$ for some numbers $r_{LN},r_1$; \item $R_2 =q \cdot y + r_2$ and $LN = q \cdot 4+r_{LN}$ and $p > y+4$ for some numbers $r_2,r_{LN} < q$; \item For each $p' < q$ such that $p'$ divides $q$ there are $r_{LN},r_1,r_2,r_3,r_{LN}',r_1',r_2',r_3', \linebreak[3] r_{LN}'', \linebreak[3] r_1'',r_2'',r_3'', r_{LN}''',r_1''',r_2''',r_3'''$ such that \begin{itemize} \parsep0pt \parskip0pt \itemsep1pt \item $r_{LN}

t$
for all $t \in \mathbb N$.
Note that the set of all $(e,x,t)$ with $Time(e,x) \leq t$
is recursive.
\ownsmallpar
Now define $f(i,j,x)$ as follows: If $Time(i,x)$ is defined and it
furthermore holds that $Time(j,j) > Time(i,x)+x$
then $f(i,j,x) = \varphi_i(x)$ else $f(i,j,x)$ remains undefined.
\ownsmallpar
The function $f$ is partial recursive. The function $f$ does
the following: if $\varphi_i(x)$ halts and furthermore
$\varphi_j(j)$ does not halt within $Time(i,x)+x$
then $f(i,j,x) = \varphi_i(x)$ else $f(i,j,x)$ is undefined.
By Proposition~\ref{pr:smn}, there is a function $g$ such that
$$
\forall i,j,x\,[\varphi_{g(i,j)}(x) = f(i,j,x)]
$$
where again equality holds if either both sides of the equality are defined
and equal or both sides are undefined.
\ownsmallpar
Now consider any $i \in I$. For all $j$ with $\varphi_j(j)$ being undefined,
it holds that
$$
\varphi_i = \varphi_{g(i,j)}
$$
and therefore $g(i,j) \in I$. The complement of the diagonal halting problem
is not recursively enumerable while the set $\{j: g(i,j) \in I\}$ is
recursively enumerable; thus there must be a $j$ with $g(i,j) \in I$
and $\varphi_j(j)$ being defined. For this $j$, it holds that
$\varphi_{g(i,j)}(x)$ is defined iff $Time(e,x)+x < Time(j,j)$.
This condition can be tested effectively
and the condition is not satisfied for any $x \geq Time(j,j)$.
Thus one can compute an explicit list $(x_1,y_1,\ldots,x_n,y_n)$
such that $\varphi_{g(i,j)}(x)$ is defined and takes the value $y$
iff there is an $m \in \{1,\ldots,n\}$ with $x = x_m$ and $y = y_m$.
There is an algorithm which enumerates all these lists, that is,
the set of these lists is recursively enumerable.
This list satisfies therefore the following:
\begin{itemize}
\parsep0pt \parskip0pt \itemsep1pt
\item If $i \in I$ then a there is a list $(x_1,y_1,\ldots,x_n,y_n)$
enumerated such that
$\varphi_i(x_1) = y_1,\ldots,\varphi_i(x_n) = y_n$; note that this
list might be empty $(n=0)$, for example
in the case that $\varphi_i$ is everywhere undefined;
\item If $(x_1,y_1,\ldots,x_n,y_n)$ appears in the list then there is
an index $i \in I$ such that $\varphi_i(x)$ is defined and equal to $y$
iff there is an $m \in \{1,\ldots,n\}$ with $x_m = x$ and $y_m = y$.
\end{itemize}
What is missing is that all functions extending a tuple from the list have
also their indices in $I$. So consider any tuple
$(x_1,y_1,\ldots,x_n,y_n)$ in the list and any function $\varphi_i$
extending this tuple. Now consider the following
partial function $f'$: $f'(j,x) = y$ iff either there is an
$m \in \{1,\ldots,n\}$ with $x_m = x$ and $y_m = y$ or $\varphi_j(j)$
is defined and $\varphi_i(x) = y$. There is a recursive function $g'$
with $\varphi_{g'(j)}(x) = f'(j,x)$ for all $j,x$; again either both
sides of the equation are defined and equal or both sides are undefined.
Now the set $\{j: g'(j) \in I\}$ is recursive enumerable and it contains
all $j$ with $\varphi_j(j)$ being undefined; as the diagonal halting problem
is not recursive, the set $\{j: g'(j) \in I\}$ is a proper superset of
$\{j: \varphi_j(j)$ is undefined$\}$. As there are only indices for two
different functions in the range of $g$, it follows that
$\{j: g'(j) \in I\} = \mathbb N$. Thus $i \in I$ and the set $I$
coincides with the set of all indices $e$ such that some finite list
$(x_1,y_1,\ldots,x_n,y_n)$ is enumerated with $\varphi_e(x_m)$
being defined and equal to $y_m$ for all $m \in \{1,\ldots,n\}$.
This completes part {\bf (b)}.
\ownpar
Second for the case {\bf (a)}, it is obvious that $\emptyset$ and
$\mathbb N$ are recursive index sets. So assume now that $I$ is
a recursive index set. Then both $I$ and ${\mathbb N}-I$ are
recursively enumerable. One of these sets, say $I$, contains
an index $e$ of the everywhere undefined function. By part {\bf(b)},
the enumeration of conditions to describe the indices $e$ in the
index set $I$ must contain the empty list. Then every index $e$
satisfies the conditions in this list and therefore $I = \mathbb N$.
Thus $\emptyset$ and $\mathbb N$ are the only two recursive
index sets.~\qed
\ownnum{Corollary} \it
There are arithmetic sets which are not recursively enumerable.\rm
\ownword{Proof.}
Recall that the halting problem
$$
H = \{(e,x): \varphi_e(x) \mbox{ is defined}\}
$$
is definable in arithmetic. Thus also the set
$$
\{e: \forall x\,[(e,x) \in H]\}
$$
of indices of all total functions is definable in arithmetic by adding
one more quantifier to the definition, namely the universal one over
all $x$. If this set would be recursively enumerable then there would
recursive enumeration of lists of finite conditions such that when
a function satisfies one list of conditions then it is in the index
set. However, for each such list there is a function with finite domain
satisfying it, hence the index set would contain an index of a function
with a finite domain, in contradiction to its definition.
Thus the set
$$
\{e: \forall x\,[(e,x) \in H]\}
$$
is not recursively enumerable.~\qed
\ownpar
The proof of Rice's Theorem and also the above proof have implicitly
used the following observation.
\ownnum{Observation} \it
If $A,B$ are sets and $B$ is recursively enumerable and if there is
a recursive function $g$ with $x \in A \Leftrightarrow g(x) \in B$
then $A$ is also recursively enumerable.\rm
\ownpar
Such a function $g$ is called a many-one reduction. Formally this
is defined as follows.
\ownnum{Definition} \it
A set $A$ is many-one reducible to a set $B$ iff
there is a recursive function $g$ such that, for all $x$,
$x \in A \Leftrightarrow g(x) \in B$.\rm
\ownpar
One can see from the definition: Assume that $A$ is many-one reducible
to $B$. If $B$ is recursive so is $A$; if $B$ is recursively enumerable
so is $A$. Thus a common proof method to show that some set $B$ is not
recursive or not recursively enumerable is to find a many-one reduction
from some set $A$ to $B$ where the set $A$ is not recursive or recursively
enumerable, respectively.
\ownnum{Example}
The set $E = \{e: \forall$ even $x\,[\varphi_e(x)$ is defined$]\}$ is
not recursively enumerable. This can be seen as follows:
Define $f(e,x)$ such that $f(e,2x) = f(e,2x+1) = \varphi_e(x)$ for
all $e,x$. Now there is a recursive function $g$ such that
$\varphi_{g(e)}(x) = f(e,x)$ for all $x$; furthermore,
$\varphi_{g(e)}(2x) = \varphi_e(x)$ for all $e,x$.
It follows that $\varphi_e$ is total iff $\varphi_{g(e)}$ is defined
on all even inputs. Thus the set of all indices of total functions
is many-one reducible to $E$ via $g$ and therefore $E$ cannot
be recursively enumerable.
\ownnum{Example}
The set $F = \{e: \varphi_e$ is somewhere defined$\}$ is not
recursive. There is a partial recursive function $f(e,x)$ with
$f(e,x) = \varphi_e(e)$ for all $e,x$ and a recursive function $g$
with $\varphi_{g(e)}(x) = f(e,x) = \varphi_e(e)$ for all $e$.
Now $e \in K$ iff $g(e) \in F$ and thus $F$ is not recursive.
\ownnum{Theorem} \it
Every recursively enumerable set is many-one reducible
to the diagonal halting problem $K = \{e: \varphi_e(e)$
is defined$\}$.\rm
\ownword{Proof.}
Assume that $A$ is recursively enumerable. Now there
is a partial recursive function $\tilde f$ such that
$A$ is the domain of $\tilde f$. One adds to $\tilde f$
one input parameter which is ignored and obtains a
function $f$ such that $f(e,x)$ is defined
iff $e \in A$. Now there is a recursive function
$g$ such that
$$
\forall e,x\,[\varphi_{g(e)}(x) = f(e,x)].
$$
If $e \in A$ then
$\varphi_{g(e)}$ is total and $g(e) \in K$;
if $e \notin A$ then
$\varphi_{g(e)}$ is nowhere defined and $g(e) \notin K$.
Thus $g$ is a many-one reduction from $A$ to $K$.~\qed
\ownnum{Exercise} \it
Show that the set $F = \{e: \varphi_e$ is defined on at least one $x\}$
is many-one reducible to the set $\{e: \varphi_e(x)$ is defined for
exactly one input $x\}$.\rm
\ownnum{Exercise} \it
Determine for the following set whether it is recursive,
recursively enumerable and non-recursive or even
not recursively enumerable:
$A = \{e: \forall x\,[\varphi_e(x)$ is defined iff $\varphi_x(x+1)$ is
undefined$]\}$.\rm
\ownnum{Exercise} \it
Determine for the following set whether it is recursive,
recursively enumerable and non-recursive or even
not recursively enumerable:
$B = \{e:$ There are at least five numbers $x$ where $\varphi_e(x)$
is defined$\}$.\rm
\ownnum{Exercise} \it
Determine for the following set whether it is recursive,
recursively enumerable and non-recursive or even
not recursively enumerable:
$C = \{e:$ There are infinitely many $x$ where $\varphi_e(x)$
is defined$\}$.\rm
\ownnum{Exercise} \it
Assume that $\varphi_e$ is an acceptable numbering. Now define
$\psi$ such that
$$
\psi_{(d+e)\cdot(d+e+1)/2+e}(x) = \cases{
undefined & if $d = 0$ and $x = 0$; \cr
d-1 & if $d > 0$ and $x = 0$; \cr
\varphi_e(x) & if $x > 0$. \cr }
$$
Is the numbering $\psi$ enumerating all partial recursive functions?
Is the numbering $\psi$ an acceptable numbering?\rm
\ownnum{Exercise} \it
Is there a numbering $\vartheta$ with the following properties:
\begin{itemize}
\parsep0pt \parskip0pt \itemsep1pt
\item The set $\{e: \vartheta_e$ is total$\}$ is recursively enumerable;
\item Every partial recursive function $\varphi_e$ is equal
to some $\vartheta_d$.
\end{itemize}
Prove the answer.\rm
\newpage
\section{Undecidability and Formal Languages}
\noindent
The current section uses methods from the previous sections
in order to show that certain problems in the area of formal
languages are undecidable. Furthermore, this section adds another
natural concept to describe recursively enumerable languages:
they are those which are generated by some grammar.
For the corresponding constructions, the notion of the
register machine will be adjusted to the multi counter machine
with respect to two major changes: the commands will be made
much more simpler (so that computations / runs can easily be
coded using grammars) and the numerical machine is adjusted
to the setting of formal languages and reads the input in like
a pushdown automaton (as opposed to register machines which
have the input in some of the registers). There are one counter
machines and multi counter machines; one counter machines are
weaker than deterministic pushdown automata, therefore the natural
concept is to allow several (``multi'') counters.
\ownnumnameonly{Description}{Multi Counter Automata} \label{de:mca}
One can modify the pushdown automaton to counter automata, also called
counter machines.
Counter automata are like register machines and Turing machines
controlled by line numbers or states (these concepts are isomorphic);
the difference to register machines are the following two:
\begin{itemize}
\parsep0pt \parskip0pt \itemsep1pt
\item The counters (= registers) have much more restricted operations:
One can add or subtract $1$ or compare whether they are $0$. The initial
values of all counters is $0$.
\item Like a pushdown automaton, one can read one symbol from the
input at a time; depending on this symbol, the automaton can go
to the corresponding line. One makes the additional rule that a
run of the counter automaton is only valid iff the full input was
read.
\item The counter automaton can either output symbols with a special
command (when computing a function) or terminate in lines with
the special commands ``ACCEPT'' and ``REJECT'' in the case that no
output is needed but just a binary decision.
Running forever is also interpreted as rejection and in some cases
it cannot be avoided that rejection is done this way.
\end{itemize}
Here an example of a counter automaton which reads inputs and checks
whether at each stage of the run, at least as many $0$ have been seen so
far as $1$.
\begin{enumerate}[\mbox{\mbox{ } \ Line} 1:]
\parsep0pt \parskip0pt \itemsep1pt
\item Counter Automaton Zeroone;
\item Input Symbol -- Symbol $0$: Goto Line 3; Symbol $1$: Goto Line 4;
No further Input: Goto Line 7;
\item $R_1 = R_1+1$; Goto Line 2;
\item If $R_1 = 0$ Then Goto Line 6;
\item $R_1 = R_1-1$; Goto Line 2;
\item REJECT;
\item ACCEPT.
\end{enumerate}
A run of the automaton on input $001$ would look like this:
\begin{verbatim}
Line: 1 2 3 2 3 2 4 5 2 7
Input: 0 0 1 -
R1: 0 0 0 1 1 2 2 2 1 1
\end{verbatim}
A run of the automaton on input $001111000$ would look like this:
\begin{verbatim}
Line: 1 2 3 2 3 2 4 5 2 4 5 2 4 6
Input: 0 0 1 1 1
R1: 0 0 0 1 1 2 2 2 1 1 1 0 0 0
\end{verbatim}
Note that in a run, the values of the register per cycle always
reflect those before going into the line; the updated values of the
register are in the next columnl. The input reflects the
symbol read in the line (if any) where ``-'' denotes the case
that the input is exhausted.
\ownnum{Theorem} \it
Register machines can be translated into counter machines.\rm
\ownword{Proof Idea.}
The main idea is that one can simulate addition, subtraction,
assignment and comparison using additional registers. Here an
example on how to translate the sequence $R_1 = R_2+R_3$ into a
code segment which uses an addition register $R_4$ which is
$0$ before and after the operation.
\begin{enumerate}[\mbox{\mbox{ } \ Line} 1:]
\parsep0pt \parskip0pt \itemsep1pt
\item Operation $R_1 = R_2+R_3$ on Counter Machine
\item If $R_1 = 0$ Then Goto Line 4;
\item $R_1 = R_1-1$; Goto Line 2;
\item If $R_2 = 0$ Then Goto Line 6;
\item $R_4 = R_4 + 1$; $R_2 = R_2-1$; Goto Line 4;
\item If $R_4 = 0$ Then Goto Line 8;
\item $R_1 = R_1+1$; $R_2 = R_2 + 1$; $R_4 = R_4-1$; Goto Line 6;
\item If $R_3 = 0$ Then Goto Line 10;
\item $R_4 = R_4 + 1$; $R_3 = R_3-1$; Goto Line 8;
\item If $R_4 = 0$ Then Goto Line 12;
\item $R_1 = R_1+1$; $R_3 = R_3 + 1$; $R_4 = R_4-1$; Goto Line 10;
\item Continue with Next Operation;
\end{enumerate}
A further example is $R_1 = 2-R_2$ which is realised by the
following code.
\begin{enumerate}[\mbox{\mbox{ } \ Line} 1:]
\parsep0pt \parskip0pt \itemsep1pt
\item Operation $R_1 = 2-R_2$ on Counter Machine
\item If $R_1 = 0$ Then Goto Line 4;
\item $R_1 = R_1-1$; Goto Line 2;
\item $R_1 = R_1+1$; $R_1 = R_1+1$;
\item If $R_2 = 0$ Then Goto Line 10;
\item $R_1 = R_1-1$; $R_2 = R_2-1$;
\item If $R_2 = 0$ Then Goto Line 9;
\item $R_1 = R_1-1$;
\item $R_2 = R_2+1$;
\item Continue with Next Operation;
\end{enumerate}
Similarly one can realise subtraction and comparison by code segments.
Note that each time one compares or adds or subtracts a variable, the
variable needs to be copied twice by decrementing and incrementing the
corresponding registers, as registers compare only to $0$ and the value
in the register gets lost when one downcounts it to $0$ so that a copy
must be counted up in some other register to save the value. This register
is in the above example $R_4$.~\qed
\ownnum{Quiz} \it
Provide counter automaton translations for the following commands:
\begin{itemize}
\parsep0pt \parskip0pt \itemsep1pt
\item $R_2 = R_2 + 3$;
\item $R_3 = R_3 - 2$;
\item $R_1 = 2$.
\end{itemize}
Write the commands in a way that that $1$ is subtracted only from registers
if those are not $0$.\rm
\ownnum{Exercise} \it
Provide a translation for a subtraction: $R_1 = R_2-R_3$. Here
the result is $0$ in the case that $R_3$ is greater than $R_2$.
The values of $R_2,R_3$ after the translated operation should be
the same as before.\rm
\ownnum{Exercise} \it
Provide a translation for a conditional jump: If $R_1 \leq R_2$ then
Goto Line 200. The values of $R_1,R_2$ after doing the conditional
jump should be the same as before the translation of the command.\rm
\ownnum{Corollary} \it
Every language recognised by a Turing machine or a register machine
can also be recognised by a counter machine. In particular there are
languages $L$ recognised by counter machines for which the membership
problem is undecidable.\rm
\ownnum{Theorem} \it \label{th:ctfintersect}
If $K$ is recognised by a counter machine then there are deterministic
context-free languages $L$ and $H$ and a homomorphism $h$ such that
$$
K = h(L \cap H).
$$
In particular, $K$ is generated by some grammar.\rm
\ownword{Proof.}
The main idea of the proof is the following: One makes $L$
and $H$ to be computations such that for $L$ the updates
after an odd number of steps and for $H$ the updates after
an even number of steps is checked; furthermore, one intersects
one of them, say $H$ with a regular language in order to
meet some other, easy to specify requirements on the computation.
\ownsmallpar
Furthermore, $h(L \cap H)$ will consist of the input words of
accepting counter machine computations; in order to achieve that
this works, one requires that counter machines read the complete
input before accepting. If they read only a part, this part is
the accepted word, but no proper extension of it.
\ownsmallpar
Now for the detailed proof, let $K$ be the given recursively enumerable set
and $M$ be a counter machine which recognises $K$. Let $R_1,R_2,\ldots,R_n$
be the registers used and let $1,2,\ldots,m$ be the line numbers used.
Without loss of generality, the alphabet used is $\{0,1\}$. One uses
$0,1$ only to denote the input symbol read in the current cycle
and $2$ to denote the outcome of a reading when the input is
exhausted. For a line $LN \in \{1,2,\ldots,m\}$, let $3^{LN}$ code the
line number. Furthermore, one codes as $4^x$ the current value of the
counter where $x = p_1^{R_1} \cdot p_2^{R_2} \cdot \ldots \cdot p_n^{R_n}$
and $p_1,p_2,\ldots,p_n$ are the first $n$ prime numbers. For example,
if $R_1 = 3$ and $R_3 = 1$ and all other registers are $0$ then
$x = 2^3 \cdot 3^0 \cdot 5^1 \cdot 7^0 \cdot \ldots = 40$.
Thus the set $I$ of all possible configurations is of the form
$$
I = \{0,1,2,\varepsilon\} \cdot \{3,33,\ldots,3^m\} \cdot \{4\}^+
$$
where the input (if requested) is the first digit then followed
by the line number coded as $3^{LN}$ then followed by the registers
coded as $4^x$; note that $x>0$ as it is the multiplication of prime
powers. Furthermore, let
$$
J = \{v \cdot w: v,w \in I
\mbox{ and $w$ is configuration of next step after } v\}
$$
be the set of all legal successor configurations. Note that $J$
is deterministic context-free: The pushdown automaton starts with
$S$ on the stack. It has several states which permit to memorise
the symbol read (if any) and the line number which is the number
of $3$ until the first $4$ comes; if this number is below $1$ or
above $m$ the pushdown automaton goes into an always rejecting state and
ignores all further inputs. Then the pushdown automaton counts the
number of $4$ by pushing them onto the stack. It furthermore reads
from the next cycle the input symbol (if any) and the new line number
and then starts to compare the $4$; again in the case that the format
is not kept, the pushdown automaton goes into an always rejecting state and
ignores all further input. Depending of the operation carried out, the
pushdown automaton compares the updated memory with the old one and
also checks whether the new line number is chosen adequately. Here some
representative sample commands and how the deterministic pushdown automaton
handles them:
\begin{description}
\parsep0pt \parskip0pt \itemsep1pt
\item{Line $i$: $R_k = R_k+1$;} \\
In this case, one has that the configuration update must
be of the form
$$ \{3^i\} \cdot \{4\}^x \cdot \{0,1,2,\varepsilon\} \cdot \{3^{i+1}\}
\cdot \{4\}^{x \cdot p_k}
$$
and the deterministic pushdown automaton checks whether the new number
of $3$ is one larger than the old one and whether when comparing the
second run of $4$ those are $p_k$ times many of the previous run, that
is, it would count down the stack only after every $p_k$-th $4$ and
keep track using the state that the second number of $4$ is a multiple of
$p_k$.
\item{Line $i$: $R_k = R_k-1$;} \\
In this case, one has that the configuration update must
be of the form
$$ \{3^i\} \cdot \{4\}^x \cdot \{0,1,2,\varepsilon\} \cdot \{3^{i+1}\}
\cdot \{4\}^{x / p_k}
$$
and the deterministic pushdown automaton checks whether the new number
of $3$ is one larger than the old one and whether when comparing the
second run of $4$ it would count down the stack by $p_k$ symbols for
each $4$ read and it would use the state to check whether the first
run of $4$ was a multiple of $p_k$ in order to make sure that the
subtraction is allowed.
\item{Line $i$: If $R_k = 0$ then Goto Line $j$;} \\
In this case, the configuration update must either be of the form
$$ \{3^i\} \cdot \{4\}^x \cdot \{0,1,2,\varepsilon\} \cdot \{3^j\}
\cdot \{4\}^{x}
$$
with $x$ not being a multiple of $p_k$ or it must be of the form
$$ \{3^i\} \cdot \{4\}^x \cdot \{0,1,2,\varepsilon\} \cdot \{3^{i+1}\}
\cdot \{4\}^{x}
$$
with $x$ being a multiple of $p_k$. Being a multiple of $p_k$ can be
checked by using the state and can be done in parallel with counting;
the preservation of the value is done accordingly.
\item{Line $i$: If input symbol is $0$ then goto Line $j_0$;
If input symbol is $1$ then goto Line $j_1$; If
input is exhausted then goto Line $j_2$;} \\
Now the configuration update must be of one of the form
$$ u \cdot \{3^i\} \cdot \{4\}^x \cdot \{0,1,2,\varepsilon\} \cdot
\{3^{j_u}\} \cdot \{4\}^x
$$
for some $u \in \{0,1,2\}$ and the deterministic pushdown automaton
can use the state to memorise $u,i$ and the stack to compare the two
occurrences of $4^x$. Again, if the format is not adhered to, the
pushdown automaton goes into an always rejecting state and ignores
all future input.
\end{description}
One can see that also the language $J^*$ can be recognised by a
deterministic pushdown automaton, as the automaton, after processing
one word from $J$, has in the case of success the stack $S$ and can
now process the next word. Thus the overall language of correct computations
is
$$
(J^* \cdot (I \cup \{\varepsilon\})) \cap
(I \cdot J^* \cdot (I \cup \{\varepsilon\})) \cap R
$$
where $R$ is a regular language which codes that the last line number
is that of a line having the command ACCEPT and that the first line number
is $1$ and the initial value of all registers is $0$ and that once
a $2$ is read from the input (for exhausted input)
then all further attempts to read an input are answered with $2$.
So if the lines $5$ and $8$ carry the command ACCEPT then
$$
R = (\{34\} \cdot I^* \cdot \{3^5,3^8\} \cdot \{4\}^+) \cap
(\{0,1,3,4\}^* \cdot \{2,3,4\}^*).
$$
As the languages $J^* \cdot (I \cup \{\varepsilon\})$
and $I \cdot J^* \cdot (I \cup \{\varepsilon\})$ are deterministic
context-free, one has also that
$L = J^* \cdot (I \cup \{\varepsilon\})$
and $H = (I \cdot J^* \cdot (I \cup \{\varepsilon\})) \cap R$
are deterministic context-free.
\ownsmallpar
Thus one can construct a context-sensitive grammar for $H \cap L$.
Furthermore, let $h$ be the homomorphism given by
$h(0) = 0$, $h(1) = 1$, $h(2) = \varepsilon$,
$h(3) = \varepsilon$ and $h(4) = \varepsilon$.
Taking into account that in an accepting computation $v$ accepting a
word $w$ all the input symbols are read, one then gets that $h(v)=w$.
Thus $h(L \cap H)$ contains all the words accepted by the counter machine
and $K = h(L \cap H)$. As $L \cap H$ are generated by a context-sensitive
grammar, it follows from Proposition~\ref{pr:grammarhomo}
that $h(L \cap H)$ is generated by some grammar.~\qed
\ownnum{Exercise} \it
In the format of the proof before and with respect to the sample multi counter
machine from Definition~\ref{de:mca}, give the encoded version
(as word from $\{0,1,2,3,4\}^+$) of the run of the machine on the
input $001$.\rm
\ownnum{Exercise} \it
In the format of the proof before and with respect to the sample multi counter
machine from Definition~\ref{de:mca}, give the encoded version
(as word from $\{0,1,2,3,4\}^+$) of the run of the machine on the
input $001111000$.\rm
\ownnum{Theorem} \it
A set $K \subseteq \Sigma^*$ is recursively enumerable iff it is
generated by some grammar. In particular, there are grammars for
which it is undecidable which words they generate.\rm
\ownword{Proof.}
If $K$ is generated by some grammar, then every word $w$ has a
derivation $S \Rightarrow v_1 \Rightarrow v_2 \Rightarrow
\ldots \Rightarrow v_n$ in this grammar. It is easy to see that
an algorithm can check, by all possible substitutions, whether
$v_m \Rightarrow v_{m+1}$. Thus one can make a function $f$
which on input $S \Rightarrow v_1 \Rightarrow v_2 \Rightarrow
\ldots \Rightarrow v_n$ checks whether all steps of the derivation
are correct and whether $v_n \in \Sigma^*$ for the given alphabet;
if these tests are passed then the function outputs $v_n$ else
the function is undefined. Thus $K$ is the range of a partial
recursive function.
\ownsmallpar
The converse direction is that if $K$ is recursively enumerable
then $K$ is recognised by a Turing machine and then $K$ is recognised
by a counter automaton and then $K$ is generated by some grammar
by the previous theorem.~\qed
\ownnum{Corollary} \it
The following questions are undecidable:
\begin{itemize}
\parsep0pt \parskip0pt \itemsep1pt
\item Given a grammar and a word, does this grammar generate the word?
\item Given two deterministic context-free languages by deterministic
push down automata, does their intersection contain a word?
\item Given a context-free language given by a grammar, does this
grammar generate $\{0,1,2,3,4\}^*$?
\item Given a context-sensitive grammar, does its
language contain any word?
\end{itemize}\rm
\ownword{Proof.}
One uses Theorem~\ref{th:ctfintersect}
and one lets $K$ be an undecidable recursively
enumerable language, say a suitable encoding of the diagonal halting
problem.
\ownsmallpar
For the first item, if one uses
a fixed grammar for $K$ and asks whether an input word is
generated by it, this is equivalent to determining the membership
in the diagonal halting problem. This problem is undecidable.
The problem where both, the grammar and the input
word, can be varied, is even more general and thus also undecidable.
\ownsmallpar
For the second item, one first produces two deterministic pushdown
automata for the languages $L$ and $H$.
Second one considers for an input word
$w = b_1 \ldots b_n \in \{0,1\}^n$ the set
\begin{quote}
$R_w = \{3,4\}^* \cdot \{b_1\} \cdot \{3,4\}^* \cdot \{b_2\} \cdot \ldots
\cdot \{3,4\}^* \cdot \{b_n\} \cdot \{2,3,4\}^*$.
\end{quote}
and notes that $L \cap H \cap R_w$ only contains accepting computations
which read exactly the word $w$.
One can construct a deterministic finite automaton for $R_w$ and combine
it with the deterministic pushdown automaton for $H$ to get
a deterministic pushdown automaton for $H_w = H \cap R_w$.
Now the question whether the intersection of $L$ and $H_w$ is
empty is equivalent to whether there is an accepting computation of the
counter machine which reads the input $w$; this question cannot be
decided. Thus the corresponding algorithm cannot exist.
\ownsmallpar
For the third item, note that the complement $\{0,1,2,3,4\}^*-(L \cap H_w)$
of $L \cap H_w$ equals to $(\{0,1,2,3,4\}^*-L) \cup (\{0,1,2,3,4\}^*-H_w)$.
The two parts of this union are deterministic context-free languages
which have context-free grammars which can be computed from the deterministic
pushdown automata for $L$ and $H_w$; these two grammars can be combined
to a context-free grammar for the union. Now being able to check whether
this so obtained context-free grammar generates all words is equivalent
to checking whether $w \notin K$ -- what was impossible.
\ownsmallpar
The fourth item is more or less the same as the second item;
given deterministic pushdown automata for $L$ and $H_w$, one can
compute a context-sensitive grammar for $L \cap H_w$. Checking whether
this grammar contains a word is as difficult as deciding whether $w \in K$,
thus impossible.~\qed
\ownpar
The above proof showed that it is undecidable to check whether a
context-free grammar generates $\{0,1,2,3,4\}^*$. Actually this is undecidable
for all alphabets with at least two symbols, so it is already undecidable
to check whether a context-free grammar generates $\{0,1\}^*$.
\ownsmallpar
A further famous undecidable but recursively enumerable problem is the
Post's Correspondence Problem. Once one has shown that this problem is
undecidable, it provides an alternative approach to show the undecidability
of the above questions in formal language theory.
\ownnumnameonly{Description}{Post's Correspondence Problem}
An instance of Post's Correspondence Problem is a list
$(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$ of pairs of words.
Such an instance has a solution iff there is a sequence
$k_1,k_2,\ldots,k_m$ of numbers in $\{1,\ldots,n\}$ such that
$m \geq 1$ -- so that the sequence is not empty -- and
$$
x_{k_1} x_{k_2} \ldots x_{k_m} = y_{k_1} y_{k_2} \ldots y_{k_m},
$$
that is, the concatenation of the words according to the indices
provided by the sequence gives the same independently of whether
one chooses the $x$-words or the $y$-words.
\ownsmallpar
Consider the following pairs: (a,a),
(a,amanap), (canal,nam), (man,lanac), (o,oo), (panama,a), (plan,nalp),
This list has some trivial solutions like $1,1,1$ giving aaa
for both words. It has also the famous solution
$2,4,1,7,1,3,6$ which gives the palindrome as a solution:
\begin{verbatim}
a man a plan a canal panama
amanap lanac a nalp a nam a
\end{verbatim}
The following instance of Post's correspondence problem does not
admit any solution: (1,0), (2,135), (328,22222), (4993333434,3333), (8,999).
The easiest way to see is that no pair can go first: the $x$-word and
the $y$-word always start with different digits.
\ownnum{Exercise} \it
For the following version of Post's Correspondence Problem, determine
whether it has a solution:
(23,45), (2289,2298), (123,1258), (777,775577), (1,9999), (11111,9).\rm
\ownnum{Exercise} \it
For the following version of Post's Correspondence Problem, determine
whether it has a solution:
(1,9), (125,625), (25,125), (5,25), (625,3125), (89,8), (998,9958).\rm
\ownnum{Exercise} \it
One application of Post's Correspondence Problem is to get a proof for
the undecidability to check whether the intersection of two deterministic
context-free languages is non-empty. For this, consider an instance of
Post's Correspondence Problem given by $(x_1,y_1),\ldots,(x_n,y_n)$
and assume that the alphabet $\Sigma$ contains the digits $1,2,\ldots,n,n+1$
plus all the symbols occurring in the $x_m$ and $y_m$. Now let
$L = \{k_m k_{m-1} \ldots k_1 (n+1) x_{k_1} x_{k_2} \ldots x_{k_m}: m > 0$ and
$k_1,k_2,\ldots,k_m \in \{1,\ldots,n\}\}$ and
$H = \{k_m k_{m-1} \ldots k_1 (n+1) y_{k_1} y_{k_2} \ldots y_{k_m}: m > 0$ and
$k_1,k_2,\ldots,k_m \in \{1,\ldots,n\}\}$.
Show that $L,H$ are deterministic context-free and that their intersection
is non-empty iff the given instance of Post's Correspondence Problem has
a solution; furthermore, explain how the corresponding deterministic
pushdown automata can be constructed from the instance.\rm
\ownnumnameonly{Description}{Non-deterministic machines}
Non-determinism can be realised in two ways: First by a not determined
transition, that is, a Goto command has two different lines and the
machine can choose which one to take or the Turing machine has in the
table several possible successor states for some combination where it
choses one. The second way to implement non-determinism is to say that
a register or counter has a value $x$ and the machine replaces $x$ by
some arbitrary value from $\{0,1,\ldots,x\}$. In order to avoid too
much computation power, the value should not go up by guessing.
Non-deterministic machines can have many computations which either
and in an accepting state (with some output) or in a rejecting state
(where the output is irrelevant) or which never halt (when again all
contents in the machine registers or tape is irrelevant). One defines
the notions as follows:
\begin{itemize}
\parsep0pt \parskip0pt \itemsep1pt
\item A function $f$ computes on input $x$ a value $y$ iff there is
an accepting run which produces the output $y$ and every further
accepting run produces the same output; rejected runs and non-terminating
runs are irrelevant in this context.
\item A set $L$ is recognised by a non-deterministic machine iff for every
$x$ it holds that $x \in L$ iff there is an accepting run of the machine
for this input $x$.
\end{itemize}
One can use non-determinism to characterise the regular and context-sensitive
languages via Turing machines or register machines.
\ownnum{Theorem} \it
A language $L$ is context-sensitive iff there is a Turing machine which
recognises $L$ and which modifies only those cells on the Turing tape
which are occupied by the input iff there is a non-deterministic
register machine recognising the language and a constant $c$
such that the register machine on any run for an input consisting of $n$
symbols never takes in its registers values larger than $c^n$.\rm
\ownpar
These machines are also called linear bounded automata as they are
Turing machines whose workspace on the tape is bounded linearly in
the input. One can show that a linear bound on the input and working
just on the cells given as an input is not giving a different model.
An open problem is whether in this characterisation the word
``non-deterministic'' can be replaced by ``deterministic'', as it
can be done for finite automata.
\ownnum{Theorem} \it \label{th:lineartimeturing}
A language $L$ is regular iff there is a non-deterministic
Turing machine and a linear bound
$a \cdot n+b$ such that the Turing machine makes for each input consisting
of $n$ symbols in each run at most $a \cdot n+b$ steps and recognises $L$.\rm
\ownpar
Note that Turing machines can modify the tape on which the input is
written while a deterministic finite automaton does not have this
possibility. This result shows that, on a linear time constraint,
this possibility does not help. This result is for Turing machines
with one tape only; there are also models where Turing machines have
several tapes and such Turing machines can recognise the set of palindromes
in linear time though the set of palindromes is not regular.
In the above characterisation, one can replace ``non-deterministic Turing
machine'' by ``deterministic Turing machine''; however, the result is
stated here in the more general form.
\ownnum{Example}
Assume that a Turing machine has as input alphabet the decimal digits
$0,1,\ldots,9$ and as tape alphabet the additional blanc $\sqcup$.
This Turing machine does the following: For an input word $w$,
it goes four times over the word from left to right and replaces
it a word $v$ such that $w = 3v+a$ for $a \in \{0,1,2\}$ in decimal
notation; in the case that doing this in one of the passes results
in an $a \notin \{0,1,2\}$, the Turing machine aborts the computation
and rejects. If all four passes went through without giving a non-zero
remainder, the Turing machine checks
whether the resulting word is of the from the set $\{0\}^* \cdot \{110\}
\cdot \{0\}^* \cdot \{110\} \cdot \{0\}^*$.
\ownsmallpar
One detail, left out in the overall description is how the pass divides
by $3$ when going from the front to the end. The method to do this is to
have a memory $a$ which is the remainder-carry and to initialise it with
$0$. Then, one replaces in each step the current decimal digit $b$
by the value $(a \cdot 10+b)/3$ where this value is down-rounded to the
next integer (it is from $\{0,1,\ldots,9\}$) and the new value of
$a$ is the remainder of $a \cdot 10+b$ by $3$. After the replacement
the Turing machine goes right.
\ownsmallpar
Now one might ask what language recognised by this Turing machine is.
It is the following: $\{0\}^* \cdot \{891\} \cdot \{0\}^* \cdot \{891\}
\cdot \{0\}^+$.
Note that $110$ times $3^4$ is $8910$ and therefore the trailing $0$
must be there. Furthermore, the nearest the two blocks of $110$ can
be is $110110$ and that times $81$ is $8918910$. Thus it might
be that there is no $0$ between the two words $891$.\rm
\ownnum{Exercise} \it
Assume that a Turing machine does the following: It has $5$ passes
over the input word $w$ and at each pass, it replaces the current
word $v$ by $v/3$. In the case that during this process of dividing
by $3$ a remainder different from $0$ occurs for the division of
the full word, then computation is aborted as rejecting.
If all divisions go through and the resulting word $v$ is
$w/3^5$ then the Turing machine adds up the digits and accepts
iff the sum of digits is exactly $2$ --- note that it can reject
once it sees that the sum is above $3$ and therefore this process
can be done in linear time with constant memory. The resulting
language is regular by Theorem~\ref{th:lineartimeturing}.
Determine a regular expression for this language.\rm
\ownnum{Exercise} \it
A Turing machine does two passes over a word and divides it the decimal
number on the tape each time by $7$.
It then accepts iff the remainders of the two divisions
sum up to $10$, that is, either one pass has remainder $4$
and the other has remainder $6$ or both passes have remainder $5$.
Note that the input for the second pass is the downrounded fraction
of the first pass divided by $7$. Construct a dfa for this
language.\rm
\ownnum{Exercise} \it
Assume that a Turing machine checks one condition, does a pass on the
input word from left to right modifying it and then again checks the
condition. The precise activity is the following on a
word from $\{0,1,2\}^*$:
\ownsmallpar
Initialise $c=0$ and update $c$ to $1-c$ whenever a
$1$ is read (after doing the replacement). For each symbol do the following
replacement and then go right:
\begin{quote}
If $c=0$ then $1 \rightarrow 0, 2 \rightarrow 1, 0 \rightarrow 0$;\\
If $c=1$ then $1 \rightarrow 2, 2 \rightarrow 2, 0 \rightarrow 1$.
\end{quote}
Here an example:
\begin{verbatim}
Before pass 0100101221010210
After pass 0011200222001220
\end{verbatim}
The Turing machine accepts if before the pass there are an even number of
$1$ and afterwards there are an odd number of $1$.
\ownsmallpar
Explain what the language recognised by this Turing machine is and
why it is regular. As a hint: interpret the numbers as natural numbers
in ternary representation and analyse what the tests and the operations do.\rm
\newpage
\ownnum{Selftest} \label{st:eightteenone}
Provide a register machine program which computes the Fibonacci sequence.
Here Fibonacci$(n) = n$ for $n<2$ and Fibonacci$(n) =
\mbox{Fibonacci}(n-1)+\mbox{Fibonacci}(n-2)$ for $n \geq 2$.
On input $n$, the output is Fibonacci$(n)$.
\ownnum{Selftest} \label{st:eightteentwo}
Define by structural induction a function $F$ such that
$F(\sigma)$ is the shortest string, if any, of the language
represented by the regular expression $\sigma$. For this,
assume that only union, concatenation, Kleene Plus and Kleene
Star are permitted to combine languages. If $\sigma$ represents
the empty set then $F(\sigma) = \infty$.
For example, $F(\{0011,000111\}) = 4$ and $F(\{00,11\}^+) = 2$.
\ownnum{Selftest} \label{st:eightteenthree}
Construct a context-sensitive grammar for all words in $\{0\}^+$
which have length $2^n$ for some $n$.
\ownnum{Selftest} \label{st:eightteenfour}
Construct a deterministic finite automaton recognising the
language of all decimal numbers $x$ which are multiples of $3$ but
which are not multiples of $10$. The deterministic finite automaton
should have as few states as possible.
\ownnum{Selftest} \label{st:eightteenfive}
Determine, in dependence of the number of states of a non-determi\-nis\-tic
finite automaton, the best possible constant which can be obtained for
the following weak version of the pumping lemma:
There is a constant $k$ such that, for all words $w \in L$ with $|w| \geq k$,
one can split $w = xyz$ with $y \neq \varepsilon$ and $xy^*z \subseteq L$.
Prove the answer.
\ownnum{Selftest} \label{st:eightteensix}
Which class $C$ of the following classes of languages is not closed under
intersection: regular, context-free, context-sensitive and recursively
enumerable? Provide an example of languages which are in $C$ such that
their intersection is not in $C$.
\ownnum{Selftest} \label{st:eightteenseven}
Provide a homomorphism $h$ which maps $001$ and $011$ to words which differ
in exactly two digits and which satisfies that $h(002) = h(311)$
and $|h(23)| = |h(32)|$.
\ownnum{Selftest} \label{st:eightteeneight}
Translate the following grammar into the normal form of linear grammars:
$$
(\{S\},\{0,1,2\},\{S \rightarrow 00S11|222\},S).
$$
Furthermore, explain which additional changes one would to carry out
in order to transform the linear normal form into Chomsky normal form.
\ownnum{Selftest} \label{st:eightteennine}
Consider the grammar $$(\{S,T,U\},\{0,1\},\{S \rightarrow ST | TT | 0,
T \rightarrow TU | UT | UU | 1, U \rightarrow 0\},S).$$
Use the algorithm of Cocke, Kasami and Younger to check whether
$0100$ is generated by this grammar and provide the corresponding table.
\ownnum{Selftest} \label{st:eightteenten}
Let $L$ be deterministic context-free and $H$ be a regular set.
Which of the following sets is not guaranteed to be deterministic
context-free: $L \cdot H$, $H \cdot L$,
$L \cap H$ or $L \cup H$? Make the right choice and then provide
examples of $L,H$ such that the chosen set is not deterministic
context-free.
\ownnum{Selftest} \label{st:eightteeneleven}
Write a register machine program which computes the function
$x \mapsto x^8$. All macros used must be defined as well.
\ownnum{Selftest} \label{st:eightteentwelve}
The universal function $e,x \mapsto \varphi_e(x)$ is partial recursive.
Now define $\psi$ as
$\psi(e) = \varphi_e(\mu x\,[\varphi_e(x) > 2e])$;
this function is partial-recursive as one can make an algorithm which
simulates $\varphi_e(0),\varphi_e(1),\ldots$ until it finds the first
$x$ such that $\varphi_e(x)$ takes a value $y>2e$ and outputs this value
$y$; this simulation gets stuck if one of the simulated computations does
not terminate or if the corresponding input $x$ does not exist.
The range $A$ of $\psi$ is recursively enumerable. Prove that $A$ is
undecidable; more precisely, prove that the complement of $A$ is not
recursively enumerable.
\ownnum{Selftest} \label{st:eightteenthirteen}
Let $W_e$ be the domain of the function $\varphi_e$ for an acceptable
numbering $\varphi_0,\varphi_1,\ldots$ of all partial recursive functions.
Construct a many-one reduction $g$ from
$$
A = \{e: W_e \mbox{ is infinite}\}
$$
to the set
$$
B = \{e: W_e = {\mathbb N}\};
$$
that is, $g$ has to be a recursive function such that
$W_e$ is infinite iff $W_{g(e)} = {\mathbb N}$.
\ownnum{Selftest} \label{st:eightteenfourteen}
Is it decidable to test whether a context-free grammar generates
infinitely many elements of $\{0\}^* \cdot \{1\}^*$?
\newpage
\ownword{Solution for Selftest~\ref{st:eightteenone}.}
The following register program computes the Fibonacci sequence.
$R_2$ will carry the current value and $R_3,R_4$ the next two
values where $R_4 = R_2+R_3$ according to the recursive equation
of the Fibonacci sequence. $R_5$ is a counting variable which
counts from $0$ to $R_1$. When $R_1$ is reached, the value in
$R_2$ is returned; until that point, in each round, $R_3,R_4$
are copied into $R_2,R_3$ and the sum $R_4 = R_2+R_3$ is
updated.
\begin{enumerate}[\mbox{\mbox{ } \ Line} 1:]
\parsep0pt \parskip0pt \itemsep1pt
\item Function Fibonacci$(R_1)$;
\item $R_2 = 0$;
\item $R_3 = 1$;
\item $R_5 = 0$;
\item $R_4 = R_2+R_3$;
\item If $R_5 = R_1$ Then Goto Line 11;
\item $R_2 = R_3$;
\item $R_3 = R_4$;
\item $R_5 = R_5+1$;
\item Goto Line 5;
\item Return$(R_2)$.
\end{enumerate}
\ownword{Solution for Selftest~\ref{st:eightteentwo}.}
One can define $F$ as follows. For the base cases, $F$ is defined
as follows:
\begin{itemize}
\parsep0pt \parskip0pt \itemsep1pt
\item $F(\emptyset) = \infty$;
\item $F(\{w_1,w_2,\ldots,w_n\}) = \min \{|w_m|: m \in \{1,\ldots,n\}\}$.
\end{itemize}
In the inductive case, when $F(\sigma)$ and $F(\tau)$ are already known,
one defined $F(\sigma \cup \tau)$, $F(\sigma \cdot \tau)$, $F(\sigma^*)$
and $F(\sigma^+)$ as follows:
\begin{itemize}
\parsep0pt \parskip0pt \itemsep1pt
\item If $F(\sigma) = \infty$ then $F(\sigma \cup \tau) = F(\tau)$; \\
If $F(\tau) = \infty$ then $F(\sigma \cup \tau) = F(\sigma)$; \\
If $F(\sigma) < \infty$ and $F(\tau) < \infty$
then $F(\sigma \cup \tau) = \min\{F(\sigma),F(\tau)\}$;
\item If $F(\sigma) = \infty$ or $F(\tau) = \infty$ \\
then $F(\sigma \cdot \tau) = \infty$ \\
else $F(\sigma \cdot \tau) = F(\sigma)+F(\tau)$;
\item $F(\sigma^*) = 0$;
\item $F(\sigma^+) = F(\sigma)$.
\end{itemize}
\ownword{Solution for Selftest~\ref{st:eightteenthree}.}
The grammar contains the non-terminals $S,T,U$ and
the terminal $0$ and the start symbol $S$ and the
following rules:
$S \rightarrow 0 | 00 | T0U$,
$T \rightarrow TV$,
$V0 \rightarrow 00V$,
$VU \rightarrow 0U$,
$T \rightarrow W$,
$W0 \rightarrow 00W$,
$WU \rightarrow 00$.
Now $S \Rightarrow T0U \Rightarrow W0U \Rightarrow 00WU \Rightarrow 0000$
generates $0^4$. Furthermore, one can show by induction on $n$ that
$S \Rightarrow^* T0^{2^n-1}U \Rightarrow TV 0^{2^n-1} U
\Rightarrow^* T 0^{2^{n+1}-2}VU \Rightarrow T0^{2^{n+1}-1}U$
and $S \Rightarrow^* T0^{2^n-1} U \Rightarrow W0^{2^n-1}U
\Rightarrow^* 0^{2^{n+1}-2}WU \Rightarrow 0^{2^{n+1}}$.
So, for each $n$, one can derive $0^{2^{n+1}}$ and one can
also derive $0,00$ so that all words from $\{0\}^+$ of
length $2^n$ can be derived.
\ownword{Solution for Selftest~\ref{st:eightteenfour}.}
The deterministic finite automaton needs to memorise two facts:
the remainder by three and whether the last digit was a $0$; the
latter needs only to be remembered in the case that the number is
a multiple of $3$. So the dfa has four states: $s,q_0,q_1,q_2$
where $s$ is the starting state and $q_0,q_1,q_2$ are the states
which store the remainder by $3$ of the sum of the digits seen so far.
The transition from state $s$ or $q_a$ $(a \in \{0,1,2\})$ on input
$b \in \{0,1,2,3,4,5,6,7,8,9\}$ is as follows (where also $a=0$ in the case
that the state is $s$):
\begin{itemize}
\parsep0pt \parskip0pt \itemsep1pt
\item If $a+b$ is a multiple of $3$ and $b = 0$ then the next
state is $s$;
\item If $a+b$ is a multiple of $3$ and $b \neq 0$ then the next
state is $q_0$;
\item If $a+b$ has the remainder $c \in \{1,2\}$ modulo $3$ then
the next state is $q_c$.
\end{itemize}
Furthermore, $s$ is the start state and $q_0$ is the only accepting
state.
\ownword{Solution for Selftest~\ref{st:eightteenfive}.}
Assume that $L$ is recognised by a non-deterministic finite
automaton having $n$ states. Then the following holds:
For every word $w \in L$ of length $n$ or more, one can
split $w = xyz$ such that $y \neq \varepsilon$ and
$x y^* z \subseteq L$. For this one considers an accepting run
of the nfa on the word $w$ which is a sequence
$q_0 q_1 \ldots q_n$ of states where $q_m$ is the state
after having processed $m$ symbols, so $q_0$ is the initial
state. The state $q_n$ must be accepting. As there are $n+1$
values $q_0,q_1,\ldots,q_n$ but only $n$ states in the automaton,
there are $i,j$ with $0 \leq i < j \leq n$ such that $q_i = q_j$.
Now let $x$ be the first $i$ symbols of $w$, $y$ be the next
$j-i$ symbols and $z$ be the last $n-j$ symbols of $w$,
clearly $w = xyz$ and $|y| = j-i > 0$. It is easy to see that
when $y$ is omitted then $q_0 q_1 \ldots q_i q_{j+1} \ldots q_n$
is a run of the automaton on $xz$ and if $y$ is repeated,
one can repeat the sequence from $q_i to q_j$ accordingly.
So $q_0 \ldots q_i (q_{i+1} \ldots q_j)^3 q_{j+1} \ldots q_n$
is an accepting run on $xy^3z$. Thus all words in $xy^*z$ are
accepted by the non-deterministic finite automaton and $xy^*z \subseteq L$.
\ownsmallpar
Furthermore, there are for each $n$ finite automata with $n$ states which
accept all words having at most $n-1$ symbols, they advance from one state
to the next upon reading a symbol and get stuck once all states are
used up. Thus the pumping constant cannot be
$n-1$, as otherwise the corresponding language would need to have
infinitely many words, as a word of length $n-1$ could be pumped.
So $n$ is the optimal constant.
\ownword{Solution for Selftest~\ref{st:eightteensix}.}
The context-free languages are not closed under intersection.
The example is the language $\{0^n1^n2^n: n \in {\mathbb N}\}$
which is the intersection of the two context-free languages
$\{0^n1^n2^m: n,m \in {\mathbb N}\}$ and
$\{0^n1^m2^m: n,m \in {\mathbb N}\}$. Both languages are
context-free; actually they are even linear languages.
\ownword{Solution to Selftest~\ref{st:eightteenseven}.}
One can choose the homomorphism given by $h(0) = 55$, $h(1) = 66$,
$h(2) = 6666$ and $h(3) = 5555$. Now $h(001) = 555566$ and
$h(011) = 556666$ so that they differ in two positions and
$h(002) = h(311) = 55556666$. Furthermore, $|h(23)| = |h(32)|$
is true for every homomorphism and a vacuous condition.
\ownword{Solution to Selftest~\ref{st:eightteeneight}.}
The grammar can be translated into the normal form for linear
grammars as follows: The non-terminals are $S,S',S'',S''',S''',T,T'$
and the rules are
$S \rightarrow 0S' | 2T$,
$S' \rightarrow 0S''$,
$S'' \rightarrow S'''1$,
$S''' \rightarrow S1$,
$T \rightarrow 2T'$,
$T' \rightarrow 2$.
\ownsmallpar
For Chomsky Normal form one would have to introduce two further
non-terminals $V,W$ representing $0$ and $1$ and use that
$T' \rightarrow 2$. Then one modifies the grammar such that
the terminals do not appear in any right side with two non-terminals.
The updated rules are the following:
$S \rightarrow VS' | T'T$,
$S' \rightarrow VS''$,
$S'' \rightarrow S'''W$,
$S''' \rightarrow SW$,
$T \rightarrow T'T'$,
$T' \rightarrow 2$,
$V \rightarrow 0$,
$W \rightarrow 1$.
\ownword{Solution for Selftest~\ref{st:eightteennine}.}
The given grammar is $(\{S,T,U\},\{0,1\},
\{S\rightarrow ST | TT |\linebreak[3] 0, \linebreak[3]
T \rightarrow TU | UT | UU | 1, U \rightarrow 0\},S)$.
Now the table for the word $0100$ is the following:
\begin{center}
\begin{tabular}{lllllll}
&&&$E_{1,4} = \{S,T\}\bs$ &&& \\
&&$E_{1,3} = \{S,T\}\bs$ && $E_{2,4}=\{S,T\}\bs$&& \\
&$E_{1,2} = \{S,T\}\bs$&&$E_{2,3} = \{T\}\bs$&&$E_{3,4} = \{T\}\bs$&\\
$E_{1,1} = \{S,U\}\bs$ && $E_{2,2} = \{T\}\bs$ && $E_{3,3} = \{S,U\}\bs$ &&
$E_{4,4} = \{S,U\}\bs$ \\
$0$ && $1$ && $0$ && $0$
\end{tabular}
\end{center}
As $S \in E_{1,4}$, the word $0100$ is in the language.
\ownword{Solution for Selftest \ref{st:eightteenten}.}
If $L$ is deterministic context-free and $H$ is regular
then $L \cap H$, $L \cup H$ and $L \cdot H$ are deterministic
context-free. However, the set $H \cdot L$ might not be
deterministic context-free. An example is the following set:
$H = (\{0\}^* \cdot \{1\}) \cup \{\varepsilon\}$ and
$L = \{0^n 1 0^n: n \in {\mathbb N}\}$. $L$ is one of the standard
examples of deterministic context-free sets; however,
when a deterministic pushdown automaton processes an input starting
with $0^n 1 0^n$, it has to check whether the number of $0$ before the
$1$ and after the $1$ are the same and therefore it will erase from the
stack the information on how many $0$ are there. This is the right thing
to do in the case that the input is from $\{\varepsilon\} \cdot L$.
However, in the case that the input is from $\{0\}^* \cdot \{1\} \cdot L$,
the deterministic pushdown automaton has now to process in total an
input of the form $0^n10^n10^m$ which will be accepted iff $n=m$.
The information on what $n$ was is, however, no longer available.
\ownword{Solution for Selftest~\ref{st:eightteeneleven}.}
One first defines the function Square computing $x \mapsto x^2$.
\begin{enumerate}[\mbox{\mbox{ } \ Line} 1:]
\parsep0pt \parskip0pt \itemsep1pt
\item Function Square$(R_1)$;
\item $R_3 = 0$;
\item $R_2 = 0$;
\item $R_2 = R_2+R_1$;
\item $R_3 = R_3+1$;
\item If $R_3 < R_1$ then goto Line 4;
\item Return$(R_1)$.
\end{enumerate}
Now one defines the function $x \mapsto x^8$.
\begin{enumerate}[\mbox{\mbox{ } \ Line} 1:]
\parsep0pt \parskip0pt \itemsep1pt
\item Function Eightspower$(R_1)$;
\item $R_2 = \mbox{Square}(R_1)$;
\item $R_3 = \mbox{Square}(R_2)$;
\item $R_4 = \mbox{Square}(R_3)$;
\item Return$(R_4)$.
\end{enumerate}
\ownword{Solution for Selftest~\ref{st:eightteentwelve}.}
First note that the complement of $A$ is infinite: All elements of
$A \cap \{0,1,\ldots,2e\}$ must be from the finite set $\{\psi(0),\psi(1),
\ldots,\psi(e-1)\}$ which has at most $e$ elements, thus there must
be at least $e$ non-elements of $A$ below $2e$. If the complement of
$A$ would be recursively enumerable then ${\mathbb N}-A$ is the range
of a function $\varphi_e$ which is defined for all $x$.
Thus $\psi(e)$ would be $\varphi_e(x)$ for the first $x$ where
$\varphi_e(x) > 2e$. As the complement of $A$ is infinite, this $x$
must exist. But then $\psi(e)$ is in both: it is in $A$ by the definition
of $A$ as range of $\psi$ and it is in the range of $\varphi_e$ which
is the complement of $A$. This contradiction shows that the complement
of $A$ cannot be the range of a recursive function and therefore $A$
cannot be recursive.
\ownword{Solution for Selftest \ref{st:eightteenthirteen}.}
The task is to construct a many-one reduction $g$ from
$
A = \{e: W_e \mbox{ is infinite}\}
$
to the set
$
B = \{e: W_e = {\mathbb N}\}.
$
\ownsmallpar
For this task one first defines a partial recursive function $f$ as
follows: Let $M$ be a universal register machine which simulates on
inputs $e,x$ the function $\varphi_e(x)$ and outputs the result
iff that function terminates with a result; if the simulation does
not terminate then $M$ runs forever. Now
let $f(e,x)$ is the first number $t$ (found by exhaustive search)
such that there are at least $x$ numbers $y \in \{0,1,\ldots,t\}$
for which $M(e,y)$ terminates within $t$ computation steps.
Note that $f(e,x)$ is defined iff $W_e$ has at least $x$ elements.
There is now a recursive function $g$ such that
$\varphi_{g(e)}(x) = f(e,x)$ for all $e,x$ where either both sides
are defined and equal or both sides are undefined.
If the domain $W_e$ of $\varphi_e$ is infinite then $\varphi_{g(e)}$
is defined for all $x$ and $W_{g(e)} = {\mathbb N}$; if
the domain $W_e$ of $\varphi_e$ has exactly $y$ elements then
$f(e,x)$ is undefined for all $x > y$ and $W_{g(e)}$ is a finite
set. Thus $g$ is a many-one reduction from $A$ to $B$.
\ownword{Solution for Selftest~\ref{st:eightteenfourteen}.}
It is decidable: The way to prove it is to construct from the
given context-free grammar for some set $L$ a new grammar for the
intersection $L \cap \{0\}^* \cdot \{1\}^*$, then to convert this
grammar into Chomsky Normal form and then to run the algorithm which
checks whether this new grammar generates an infinite set.
\newpage
\fi
\ifx\csfive\yesy
\newpage
\section{Regular Languages and Learning Theory}
\noindent
Angluin \cite{An87} investigated the question on how to learn
a dfa by a dialogue between a learner (pupil) and teacher.
The learner can ask questions to the teacher about the concept
(dfa) to be learnt and the teacher answers. The learner can ask
two types of questions:
\begin{itemize}
\parsep0pt \parskip0pt \itemsep1pt
\item Is the following dfa equivalent to the one to be learnt?
\item Does the dfa to be learnt accept or reject the following word $w$?
\end{itemize}
The first type of questions are called ``equivalence queries'' and
the second type of questions are called ``membership queries''.
The teacher answers an equivalence query either with ``YES'' (then
the learner has reached the goal) or ``NO'' plus a counterexample $w$
on which the dfa given by the learner and the dfa to be learnt have
different behaviour;
the teacher answers a membership query by either ``YES'' or ``NO''.
\ownsmallpar
Theoretically, the learner could just take a listing of all dfas and
ask ``Is dfa$_1$ correct?'', ``Is dfa$_2$ correct?'', ``Is dfa$_3$ correct?''
$\ldots$ and would need $s$ equivalence queries to find out whether
dfa$_s$ is correct. This strategy is, however, very slow; as there are
more than $2^n$ dfas with $n$ states, one would for some dfas with
$n$ states need more than $2^n$ queries until the dfa is learnt.
Angluin showed that there is a much better algorithm and she
obtained the following result.
\ownnumname{Theorem}{Angluin's algorithm to learn dfas by queries}{An87}
\label{th:angluindfa} \it
There is a learning algorithm which has polynomial response time in each
step and which learns in time polynomial in the
number of states of the dfa to be learnt and the longest counterexample
given an arbitrary dfa using equivalence queries and membership queries.\rm
\ownword{Proof.}
A simplified version of Angluin's algorithm is given. The idea of Angluin
is that the learner maintains a table $(S,E,T)$ which is updated in each round.
In this table, $S$ is a set of words which represent the set of states.
$E$ consists of all the counterexamples observed plus their suffixes.
$S$ and $E$ are finite sets of size polynomial in the number and length
of counterexamples seen so far and $T$ is a function which for all
members $w \in S \cdot E \cup S \cdot \Sigma \cdot E$ says whether the
automaton to be learnt accepts or rejects $w$.
\ownsmallpar
Angluin defines the notion of a row:
For $u \in S \cup S \cdot \Sigma$,
let $(v_1,v_2,\ldots,v_k)$ be a listing
of the current elements in $E$ and for each $u \in S \cup S \cdot \Sigma$,
let the vector $row(u)$ be
$(T(uv_1),T(uv_2),\ldots,T(uv_k))$.
The table $(S,E,T)$ is called closed, if for every
$u \in S$ and $a \in \Sigma$ there is a $u' \in S$ with
$row(u') = row(ua)$.
\ownsmallpar
Now Anlguin defines for each closed $(S,E,T)$ the
finite automaton DFA$(S,E,T)$ where the set of states is $S$,
the alphabet is $\Sigma$ and the transition function finds to a state $u$
and $a \in \Sigma$ the unique $u' \in S$ with
$row(u') = row(ua)$. The starting state is represented by the empty word
$\varepsilon$ (which is in $S$). A state $u$ is accepting iff
$T(u) = 1$.
Note that DFA$(S,E,T)$ is complete and deterministic.
The learning algorithm is now the following.
\begin{verse}
Teacher has regular
set $L$ and learner makes membership and equivalence queries.\\
1. Initialise $S = \{\varepsilon\}$ and $E = \{\varepsilon\}$. \\
2. For all $w \in S \cdot E \cup S \cdot \Sigma \cdot E$ where
$T(w)$ is not yet defined, make a membership query to determine $L(w)$
and let $T(w) = L(w)$. \\
3. If there are $u \in S$ and $a \in \Sigma$ with $row(ua) \neq row(u')$ for
all $u' \in S$ then let $S = S \cup \{ua\}$ and go to $2$. \\
4. Make an equivalence query whether DFA$(S,E,T)$ recognises $L$. \\
5. If the answer is ``YES'' then terminate with DFA$(S,E,T)$. \\
6. If the answer is ``NO'' with counterexample $w$ then
let $E = E \cup \{v: \exists u\,[uv=w]\}$ and go to 2.
\end{verse}
Now one shows various properties in order to verify the termination of
the algorithm and the polynomial bounds on the number of membership and
equivalence queries. For this, assume
that $(Q,\Sigma,\delta,s,F)$ is the minimal dfa recognising $L$.
Now various invariants are shown.
\ownpar
{\em If $u,u'$ are different elements of $S$ then
$\delta(s,u) \neq \delta(s,u')$ as there is a word $v \in E$
with $L(uv) \neq L(u'v)$. Hence $|S| \leq |Q|$
throughout the algorithm.}
\ownpar
{\em If $(S,E,T)$ is closed and $w \in E$ then the DFA accepts $w$
iff $w \in L$.}
\ownsmallpar
To see this, one does the following induction: Let $w = a_1 a_2 \ldots a_n$.
Clearly $T(w) = L(w)$ by the corresponding membership query.
For $m=0,1,\ldots,n$, one shows that the automaton is after processing
$a_1 a_2 \ldots a_m$ is in a state $u_m$ with
$T(u_m a_{m+1} a_{m+2} \ldots a_n) = T(w)$.
This is true for $m=0$ as $u_0 = \varepsilon$ is the initial
state of DFA$(S,E,T)$. Assume now that it is correct for $m*0 \Rightarrow \max\{b_0,b\}$ is an Anke-node)
\item or $0 < b_i < b$
\end{enumerate}
and one updates $b_i = b$ and $b_j = 0$ for all $j < i$;
\item If this update produces a non-zero $b_i$ for any $i$ with
$2^i > 2n$ then the game terminates with Anke being declared
winner.
\end{itemize}
The winning statistic of Boris is maintained and updated by the same
algorithm, with the roles of Anke and Boris being interchanged in the
algorithm. When both winning statistics are updated without a termination
then the game goes into the next round by letting the corresponding player
choose a move.
\ownsmallpar
When updating Anke's winning statistic and the update can be done
by case (a) then one can form a new
$i$-sequence by putting the $j$-sequences for $j=i-1,i-2,\ldots,1,0$
together and appending the one-node sequence $b$ which then has the length
$2^i = 2^{i-1}+2^{i-2}+\ldots+2^1+2^0+1$; in the case that $i=0$ this condition
just says that one forms a $0$-sequence of length $2^0$ just consisting of
the node $b$. Note that in the case $i>0$ the value $\max\{b_0,b\}$ is an
Anke-node and therefore the highest node between the last member $a$ of
the $F_0$-sequence and $b$ has the value $\max\{b_h,b\}$ and is an
Anke-node. Furthermore, for every $j 0$) by the new value
$b > b_i$ and one discards all $j$-sequences with $j*