Problem Set 2 latex source
This file is provided to help students create their solutions
in latex if they wish. Some formatting was removed for clarity.
It is missing some macros, but you can figure out what they are
by looking at the pdf image. It is not a working latex file.
\newcommand{\st}[1]{\mbox{\texttt{#1}}}
\newcommand{\tok}[1]{\langle \mbox{\textsc{#1}} \rangle}
\item[0.1] Read and solve, \underline{but do not turn in}: Book, 2.16 .
\ [\cfls\ closed under $\union$, $\concat$, $\kstar$] \\
Solve by using both \cfgs\ and \pdas. \\
Observe that this gives another proof that that all regular languages
are \cfls.
\item[0.2] Read and solve, \underline{but do not turn in}: Book, 2.18 .
\ [(\cfl$\inter$regular) is a \cfl] \\
Note, problems marked with ${}^\abbrevf{A}$ have solutions in the book.
\item[0.3] Read and solve, \underline{but do not turn in}: Book, 2.26 .
\ [Chomsky normal form]
\item[0.4] Read and solve, \underline{but do not turn in}: Book, 2.30c .
\ [\cfl\ Pumping lemma]
\item
Let $\Sigma=\{\st{1},\st{2},\st{3},\st{4}\}$.
\begin{enumerate}
\item Let $C=\set{w}w$ has equal numbers of \st{1}s and \st{2}s, and
equal numbers of \st{3}s and \st{4}s\setend. \\
Show that $C$ is not context free.
\item Use (a) to show that the class of \cfls\ isn't closed
under complement and intersection.
\item Let $D=C \union (\SS\SS)^*$. Is $D$ a \cfl? Prove your answer.
\item Let $E=C \union \SS(\SS\SS)^*$. Is $E$ a \cfl? Prove your answer.
\end{enumerate}
\item
Let $G = (V, \Sigma, R, \tok{stmt})$ be the following grammar.
$ \Sigma = \{\st{if}, \st{condition}, \st{then}, \st{else},
\st{a:=1}\},\\
V = \{\tok{stmt}, \tok{if-then}, \tok{if-then-else}, \tok{assign}\} $
and the rules are:
\begin{grammar}
\tok{stmt} \cfgarrow \tok{assign} \cfgor
\tok{if-then} \cfgor \tok{if-then-else} \\
\tok{if-then} \cfgarrow \st{if condition then}\; \tok{stmt} \\
\tok{if-then-else} \cfgarrow \st{if condition then}\; \tok{stmt} \;
\st{else}\; \tok{stmt} \\
\tok{assign} \cfgarrow \st{a:=1}
\end{grammar}
\begin{enumerate}
\item Show that $G$ is ambiguous.
\item Give a new unambiguous grammar that generates $L(G)$.
\ (exactly the same language) \\
(Explain how your grammar avoids the ambiguity.
A formal proof that it is unambiguous is not necessary.)
\end{enumerate}
\item
A \defin{queue automaton} is like a push-down automaton
except that the stack is replaced by a queue. A \defin{queue} is a tape
allowing symbols to be written only on the left-hand end and read only at
the right-hand end. Each write operation (we'll call it a \emph{push})
adds a symbol to the left-hand end of the queue and each read operation
(we'll call it a \emph{pull}) reads and removes a symbol at the right-hand
end. As with a \pda, the input is placed on a separate read-only
input tape, and the head on the input tape can move only from left to
right. The input tape contains a cell with a blank symbol following the
input, so that the end of the input can be detected. A queue automaton
accepts its input by entering a special accept state at any time. Show
that a language can be recognized by a deterministic queue automaton
iff the language is Turing-recognizable.
\item
Show that a language is decidable iff some enumerator enumerates
the language in string order. (\defin{String order} is the standard
length-increasing, lexicographic order, see text p 14).
\item
Let $C$ be a language. Prove that $C$ is Turing-recognizable
iff a decidable language $D$ exists such that
$C=\set{x} \exists y \in \{\st0,\!\st1\}\kstar\ (\brk{x,y} \in D) \setend$.
(Hint: You must prove both directions of the ``iff''.
The ($\longleftarrow$) direction is easier.
For the ($\longrightarrow$) direction, think of $y$ as providing
additional information that allows you to confirm when $x\in C$,
but without the possibility of looping.)
\item
Consider the problem of testing whether a pushdown automaton ever uses
its stack. Formally, let $\lang{PUSHER}=\setb{P}{P}$ is a PDA that
pushes a symbol on its stack on some (possibly non-accepting) branch
of its computation at some point on some input $w\in\SSS\setend$.
Show that $\lang{PUSHER}$ is decidable.
(Hint: Use a theorem from lecture to give a short solution.)
\item[$7.^{\!\star}$] (optional)
Let the \defin{rotational closure} of language $A$
be $\lang{RC}(A)\,{=}\,\set{yx}xy\,{\in} A$ where $x,y\,{\in}\,\SSS\setend$. \\
Show that the class of \cfls\ is closed under rotational closure.