chapter4.tex

\section{Chapter 4}
\begin{enumerate}
%		4.2		%
\item[4.2]Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
\\
\textbf{Solution:} We formulate the problem $EQ_{DFA,REX}$ = \{\angles{A, R} $|$ $A$ is a DFA, $R$ is a regular expression, and $L(A) = L(R)\}$. We will design a TM $T$ that decides $EQ_{DFA,REX}$:
\\
$T$ = ``On input \angles{A, R} where $A$ is a DFA, $R$ is a regular expression:
\begin{enumerate}
\itemsep0em
\item[1.]Use Theorem 1.54 to convert $R$ into an equivalent DFA $B$. Therefore, $L(B) = L(R)$.
\item[2.]Run $EQ_{DFA}$ on input \angles{A, B}. Output what $EQ_{DFA}$ outputs."
\end{enumerate}
Since $EQ_{DFA}$ is decidable, and the conversion from regular expressions to DFAs takes finite time, $EQ_{DFA,REX}$ is decidable.

%		4.3		%
\item[4.3]Let $ALL_{DFA}$ = \{\angles{A} $|$ $A$ is a DFA and $L(A) = \Sigma^*\}$. Show that $ALL_{DFA}$ is decidable.
\\
\textbf{Solution:} We will design a TM $T$ that decides $ALL_{DFA}$:
\\
$T$ = ``On input \angles{A} where $A$ is a DFA:
\begin{enumerate}
\itemsep0em
\item[1.]Construct a DFA $B$ such that $L(B) = \overline{L(A)}$.
\item[2.]Run $E_{DFA}$ on input \angles{B}. Output what $E_{DFA}$ outputs."
\end{enumerate}
Since $E_{DFA}$ is decidable, $ALL_{DFA}$ is decidable.

%		4.4		%
\item[4.4]Let $A\epsilon_{CFG}$ = \{\angles{G} $|$ $G$ is a CFG that generates $\epsilon$.\}. Show that $A\epsilon_{CFG}$ is decidable.
\\
\textbf{Solution:} We will design a TM $T$ that decides $A\epsilon_{CFG}$:
\\
$T$ = ``On input \angles{G} where $G$ is a CFG:
\begin{enumerate}
\itemsep0em
\item[1.]Convert $G$ into an equivalent CFG $C = (V, \Sigma, R, S)$ in Chomsky Normal Form.
\item[2.]$Accept$ \angles{G} if $C$ includes the rule $S \rightarrow \epsilon$, $reject$ \angles{G} otherwise."
\end{enumerate}
Since converting a CFG into CNF is decidable, $A\epsilon_{CFG}$ is decidable.

%		4.7		%
\item[4.7]Let $\mathcal{B}$ be the set of all infinite sequences over \{0, 1\}. Shat that $\mathcal{B}$ is uncountable using a proof by diagonalization.
\\
\textbf{Solution:} Suppose (by contradiction) that $\mathcal{B}$ is countable. Therefore, there exists a bijection $f$ between $\mathcal{B}$ and $\mathbb{N}$. For $\forall n \in \mathbb{N}$, let $f(n) = s_{n1}...s_{nk}$, where $s_{nk}$ is the $k$th bit in the $n$th sequence of $\mathcal{B}$ for $\forall{k} \in \mathbb{N}$. Define $t = t_1t_2...$ be an infinite sequence over \{0, 1\} such that $t_k = |s_{kk}-1|$ for $\forall k \in \mathbb{N}$. Therefore, $t \in \mathcal{B}$ by construction. We can see that $\nexists x \in \{0, 1\}$ such that $x = |1-x|$. Therefore, for $\forall k \in \mathbb{N}, t_k \ne |s_{kk} - 1|$. This implies that in at least 1 bit, $t$ is different than all other sequences in $\mathcal{B}$ because of $t$'s construction, which involves all other sequences in $\mathcal{B}$. This implies for $\forall n \in \mathbb{N}, f(n) \ne t$, a contradiction. Therefore, $\mathcal{B}$ is uncountable.

%		4.10		%
\item[4.10]Let $INFINITE_{DFA}$ = \{\angles{M} $|$ $M$ is a DFA and $L(M)$ is an infinite language\}. Show that $INFINITE_{DFA}$ is decidable.
\\
\textbf{Solution:} \alreadyanswered

%		4.11		%
\item[4.11]Let $INFINITE_{PDA}$ = \{\angles{M} $|$ $M$ is a PDA and $L(M)$ is an infinite language\}. Show that $INFINITE_{PDA}$ is decidable.
\\
\textbf{Solution:} We will design a TM $T$ that decides $INFINITE_{PDA}$:
\\
$T$ = ``On input \angles{M} where $M$ is a PDA:
\begin{enumerate}
\itemsep0em
\item[1.]Construct an equivalent CFG $G$ from $M$.
\item[2.]Convert $G$ into an equivalent CFG $C = (V, \Sigma, R, S)$ in Chomsky Normal Form.
\item[3.]$Accept$ \angles{M} if there exists a derivation $A \xRightarrow{+} uAv$ for some $u, v \in \Sigma^*$. Otherwise, $reject$ \angles{M}.
\end{enumerate}
Since all of the algorithms in this machine are decidable, $INFINITE_{PDA}$ is decidable.

%		4.12		%
\item[4.12]Let $A$ = \{\angles{M} $|$ $M$ is a DFA that doesn't accept any string containing an odd number of 1s\}. Show that $A$ is decidable.
\\
\textbf{Solution:} \alreadyanswered


%		4.13		%
\item[4.13]Let $A$ = \{\angles{R,S} $|$ $R$ and $S$ are regular expressions and $L(R) \subseteq L(S)\}$. Show that $A$ is decidable.
\\
\textbf{Solution:} We will design a TM $T$ that decides $A$:
\\
$T$ = ``On input \angles{R,S} where $R$ and $S$ are regular expressions:
\begin{enumerate}
\itemsep0em
\item[1.]Construct a DFA $B$ such that $L(B) = \overline{L(S)} \cap L(R)$.
\item[2.]Run $E_{DFA}$ on input \angles{B}. Output what $E_{DFA}$ outputs."
\end{enumerate}
Since $E_{DFA}$ is decidable, $A$ is decidable. This construction is correct because $L(R) \subseteq L(S) \Leftrightarrow \overline{L(S)} \cap L(R) = \varnothing$.

%		4.14		%
\item[4.14]Let $\Sigma = \{0, 1\}$. Show that the problem of determining whether a CFG generates some string in $1^*$ is decidable. In other words, show that
\begin{center}
\{\angles{G} $|$ $G$ is a CFG over \{0, 1\} and $1^* \cap L(G) \ne \emptyset$\} 
\end{center}
is a decidable language.
\\
\textbf{Solution:} \alreadyanswered

%		4.15		%
\item[4.15]Show that the problem of determining whether a CFG generates all strings in 1* is decidable. In other words, show that \{\angles{G} $|$ $G$ is a CFG over $\{0, 1\}$ and $1^* \subset L(G)$\} is a decidable language. 
\\
\textbf{Solution:} Let $f$ be a computable function. Construct a decider $D$:
\\
$D$ = ``On input \angles{G} where $G$ is a CFG:
\begin{enumerate}
\itemsep0em
\item[1.]Convert $G$ into an equivalent CFG $C$ in Chomsky Normal Form.
\item[2.]Let $p$ be the pumping length of $C$.
\item[3.]Repeat $0 \le i \le p + p!$:
\begin{enumerate}
\item[a.]Check whether $1^i \in L(C)$.
\item[b.]If not, $reject$ \angles{G}.
\end{enumerate}
\item[4.]$Accept$ \angles{G}.
\end{enumerate}
We can check $1^i \in L(C)$ using the Cocke-Younger-Kasami (CYK) algorithm for CFGs, which has a running time of $\Theta(n^3 |G|)$. Therefore, the loop has a running time of $\Theta(pn^3 |G|)$. Since Steps 1, 2, 3, and 4 take finite time, this language is decidable.

%		4.23		%
\item[4.23]Say that an NFA is ambiguous if it accepts some string along two different computation branches. Let $AMBIG_{NFA}$ = \{\angles{N} $|$ $N$ is an ambiguous NFA\}. Show that $AMBIG_{NFA}$ is decidable. (Suggestion: One elegant way to solve this problem is to construct a suitable DFA and then run $E_{DFA}$ on it.)
\\
\textbf{Solution:} \alreadyanswered

%		4.24		%
\item[4.24]A \emph{\textbf{useless state}} in a pushdown automaton is never entered on any input string. Consider the problem of determining whether a pushdown automaton has any useless states. Formulate this problem as a language and show that it is decidable.
\\
\textbf{Solution:} Let $U_{PDA}$ = \{\angles{P} $|$ $P$ is a PDA that has useless states\}. We will design a TM $T$ that decides $U_{PDA}$. First, we will define the problem $E_{PDA}$ = \{\angles{P} $|$ $P$ is a PDA and $L(P) = \varnothing$\}. We now show that $E_{PDA}$ is decidable with a decider $D$:
\\
$D$ = ``On input \angles{P} where $P$ is a PDA:
\begin{enumerate}
\itemsep0em
\item[1.]Convert $P$ into an equivalent CFG $G$.
\item[2.]Run $E_{CFG}$ on input \angles{G}. Output what $E_{CFG}$ outputs."
\end{enumerate}
This language is decidable because all steps in its construction take finite time, and $E_{CFG}$ is a decider.
\\
$T$ = ``On input \angles{P} where $P = (Q, \Sigma, \Gamma, \delta, q_0, Z, F)$ is a PDA:
\begin{enumerate}
\itemsep0em
\item[1.]For $\forall q \in Q$:
\begin{enumerate}
\item[a.]Modify $P$ such that $F = \{q\}$.
\item[b.]Run $E_{PDA}$ on input \angles{P}. If $E_{PDA}$ accepts, $accept$ \angles{P}.
\end{enumerate}
\item[2.]$Reject$ \angles{P}."
\end{enumerate}
Since $E_{PDA}$ is decidable, $U_{PDA}$ is decidable.

%		4.25		%
\item[4.25]Let $BAL_{DFA}$ = \{\angles{M} $|$ $M$ is a DFA that accepts some string containing an equal number of 0s and 1s\}. Show that $BAL_{DFA}$ is decidable. (Hint: Theorems about CFLs are helpful here.)
\\
\textbf{Solution:} \alreadyanswered

\end{enumerate}