\documentclass[12pt]{article}
\usepackage{amsfonts}
%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}

\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%\input ../basicmath/basicmathmac.tex
%
%\input ../adgeomcs/lamacb.tex
\input ../adgeomcs/mac.tex
\input ../adgeomcs/mathmac.tex

\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}
\def\buildrell#1\over#2{\mathrel{\mathop{\null#1}\limits_{#2}}}
\def\rmder#1{{\ \buildrell  \Longrightarrow \over{rm}}^{#1}\ }
\def\lmder#1{\buildrel #1\over{\buildrell  \Longrightarrow \over{lm}}}

%
\begin{document}
\begin{center}
\fbox{{\Large\bf Spring, 2009 \hspace*{0.4cm} CIS 511}}\\
\vspace{1cm}
{\Large\bf Introduction to the Theory of Computation\\
Jean Gallier \\
\vspace{0.5cm}
Homework 4}\\[10pt]
March 17, 2009; Due March 31, 2009\\
\end{center}

``A problems'' are for practice only, and should not
be turned in.

\vspace {0.25cm}
\noindent
{\bf Problem A1.} 
Given any two context-free languages
$L_1$ and $L_2$ over the same alphabet $\Sigma$, prove that
$L_1\cup L_2$ and $L_1L_2$ are also context-free.

\vspace {0.25cm}
\noindent
{\bf Problem A2.} 
Let $\Sigma$ and $\Delta$ be some alphabets, and
let $\mapdef{h}{\Sigma^*}{\Delta^*}$ be a homomorphism.
Given any language $L\subseteq \Sigma^*$,
recall that
\[h(L) = \{h(w)\in \Delta^* \ \mid \ w\in L\}.\]
Prove that if $L$ is context-free, then $h(L)$ is also
context-free.

\vspace {0.25cm}
\noindent
{\bf Problem A3.} 
Given any language $L\subseteq \Sigma^*$, let
\[L^R = \{w^R \mid w \in L\},\]
the {\it reversal language of $L$\/} (where $w^R$
denotes the reversal of the string $w$).
Prove that if $L$ is context-free, then $L^R$
is also context-free.

\vspace {0.5cm}
``B problems'' must be turned in.

\vspace{0.25cm}\noindent
{\bf Problem B1 (70 pts).} 
(i) Prove that the conclusion of the pumping lemma holds for the following
language $L$ over $\{a, b\}^*$,
and yet, $L$ is {\bf not\/} regular!
\[L = \{w \ \mid \ \exists n \geq 1,\,
\exists x_i\in a^+,\,\exists y_i\in b^+,\, 1\leq i \leq n,\,
\hbox{$n$ is not prime},\,
w = x_1y_1 \cdots x_ny_n\}.\]

\medskip
(ii)
Consider the following version of the pumping lemma.
For any regular language $L$, there is some $m \geq 1$ so that
for every $y\in \Sigma^*$, if $|y| = m$, then there exist
$u, x, v\in \Sigma^*$ so that
\begin{enumerate}
\item[(1)]
$y = uxv$;
\item[(2)]
$x\not= \epsilon$;
\item[(3)]
For all $z\in \Sigma^*$,
\[yz \in L
\quad\hbox{iff}\quad
ux^ivz\in L\]
for all $i\geq 0$.
\end{enumerate}

Prove that this pumping lemma holds.

\medskip
(iii)
Prove that the converse of the pumping lemma in (ii) also holds,
i.e., if a language $L$ satisfies the pumping lemma in (ii),
then it is regular.

\medskip
(iv)
Consider yet another version of the pumping lemma.
For any regular language $L$, there is some $m \geq 1$ so that
for every $y\in \Sigma^*$, if $|y| \geq m$, then there exist
$u, x, v\in \Sigma^*$ so that
\begin{enumerate}
\item[(1)]
$y = uxv$;
\item[(2)]
$x\not= \epsilon$;
\item[(3)]
For all $\alpha, \beta\in \Sigma^*$,
\[\alpha u\beta \in L
\quad\hbox{iff}\quad
\alpha ux^i \beta\in L\]
for all $i\geq 0$.
\end{enumerate}

Prove that this pumping lemma holds.

\medskip
(v)
Prove that the converse of the pumping lemma in (iv) also holds,
i.e., if a language $L$ satisfies the pumping lemma in (iv),
then it is regular.


\vspace{0.25cm}\noindent
{\bf Problem B2 (60 pts).} 
Let $D = (Q, \Sigma, \delta, q_0, F)$ be a {\it trim\/} DFA.
Consider the following procedure:
\begin{enumerate}
\item[(1)]
Form an NFA, $N$,  by reversing all the transitions
of $D$, i.e., there is a transition from $p$ to $q$ on
input $a\in \Sigma$ in $N$ iff $\delta(q, a) = p$ in $D$.
\item[(2)]
Apply the subset construction to the NFA, $N$, obtained in (1),
taking the start state to be the set $F$ and the only final
state of $N$ to be $\{q_0\}$. Then, trim the resulting DFA,
obtaining the DFA $D^R$. 
\end{enumerate}

Observe that $L(D^R) = L(D)^R$.

\medskip
Now, apply the above procedure to $D$, getting $D^R$, and
apply this procedure again, to get $D^{RR}$.
Prove that $D^{RR}$ is a minimal DFA for $L = L(D)$.

\medskip\noindent
{\it Hint\/}.
First prove that if $\delta_R$ is the transition function
of $D^R$, then for every $w\in \Sigma^*$ and for every
state, $T$, of $D^R$,
\[
\delta_R^*(T, w) =  \{q\in Q \mid \delta^*(q, w^R) \in T\}.
\]
%What can you say about $D^R$ if $D$ is trim?


\vspace{0.25cm}\noindent
{\bf Problem B3 (100 pts).} 
Let  $D = (Q, \Sigma, \delta, q_0, F)$ be a DFA
with $n$ states, say $q_1, \ldots, q_n$, where
$q_1$ is the start state (Note, we denote the start
state $q_1$, not $q_0$!) We associate with $D$
the $n\times n$ boolean matrix, $\Delta_D$, defined such that
\[
\Delta_D(q_i, q_j) =
\cases{
1 & if $(\exists a\in \Sigma)(\delta(q_i, a) = q_j)$, \cr
0 & otherwise. \cr
}
\]
Thus, $\Delta_D(q_i, q_j) = 1$ iff there is some edge
from $q_i$ to $q_j$ (regardless of the label of that edge).
Add and multiply matrices treating $\{0, 1\}$
as truth values, i.e.
\begin{eqnarray*}
0 + 0 & = & 0\\
0 + 1 & = & 1\\
1 + 0 & = & 1\\
1 + 1 & = & 1\\
0 0 & = & 0\\
0 1 & = & 0\\
1 0 & = & 0\\
1 1 & = & 1.
\end{eqnarray*}
(In other words, $\{0, 1\}$ is the two-element boolean ring).

\medskip
(a) 
Prove that $\Delta_D^k$ gives the $k$-step reachability
relation on $D$, i.e., 
$\Delta_D^k(q_i, q_j) = 1$ iff
$\delta^*(q_i, w) = q_j$, for some string $w\in \Sigma^*$
with $|w| = k$ (We set $\Delta_D^0 = I$, the identity
matrix).

Prove that there are only finitely many matrices
$\Delta_D^k$, where $k \geq 0$.
For any $k \geq 0$, let
\[\Delta_D^{*[k]} = I + \Delta_D + \Delta_D^2 + \cdots + 
\Delta_D^k.
\]
Prove that there is a smallest $k\leq n - 1$ so that
$\Delta_D^{*[k]} = \Delta_D^{*[k + i]}$ for all $i\geq 1$.
Let $\Delta_D^* = \Delta_D^{*[k]}$, for the above $k$.
Prove that 
$\Delta_D^*(q_i, q_j) = 1$ iff
$\delta^*(q_i, w) = q_j$, for some string $w\in \Sigma^*$.

\medskip
For simplicity of notation, from now on drop the subscript $D$ in
$\Delta_D$. 

\medskip
(b)
Prove that for any regular language, $L$, the languages
\[
L_{2^n} = \{u\in \Sigma^* \mid (\exists v\in \Sigma^*)
(|v| = 2^{|u|}\quad\hbox{and}\quad uv \in L)\}
\]
and
\[
L_{2^{2^n}} = \{u\in \Sigma^* \mid (\exists v\in \Sigma^*)
(|v| = 2^{2^{|u|}}\quad\hbox{and}\quad uv \in L)\}
\]
are also regular.

\medskip\noindent
{\it Hint\/}. Use the Myhill-Nerode theorem, i.e.,
find a suitable right-invariant equivalence relation
of finite index.


\medskip
(c)
Prove 
that for any regular language, $L$, the language
\[
L_{n^2} = \{u\in \Sigma^* \mid (\exists v\in \Sigma^*)
(|v| = |u|^2\quad\hbox{and}\quad uv \in L)\}
\]
is also regular.

\medskip\noindent
{\it Hint\/}. 
Use the Myhill-Nerode theorem.

\medskip
(d)
Let $P(n)$ be any polynomial with nonnegative integer coefficients, say \\ 
$P(n) = a_0n^d + a_1n^{d-1} + \cdots + a_d$.
Prove that for every regular language, $L$,
and any polynomial, $P(n)$, as above, the language
\[
L_P = \{u\in \Sigma^* \mid (\exists v\in \Sigma^*)(|v| = P(|u|)
\quad\hbox{and}\quad uv \in L)\}
\]
is a regular language.

\medskip\noindent
{\it Hint\/}. 
Use the Myhill-Nerode theorem.



\vspace{0.25cm}\noindent
{\bf Problem B4 (60 pts).} 
Give context-free grammars for the following languages:

\medskip
(a)
$L_{5} = \{wcw^{R}\ \mid\ w \in \{a,b\}^{*}\}$\ 
($w^{R}$ denotes the reversal of $w$)

\medskip
(b)
$L_{6} = \{a^{m}b^{n}\ \mid\ 1 \leq m \leq n \leq 2m\}$

\medskip
For any fixed integer $K\geq 2$, 

\medskip
$L_{7} = \{a^{m}b^{n}\ \mid\ 1 \leq m \leq n \leq Km\}$

\medskip
(c)
$L_{8} = \{a^{n}b^{n}\ \mid\ n \geq 1\}\cup \{a^{n}b^{2n}\ \mid\ n \geq 1\}$

\medskip
(d)
$L_{9} = \{a^{m}b^{n}a^{m}b^{p}\ \mid\ m, n, p \geq 1\}
\cup \{a^{m}b^{4n}a^{p}b^{4n}\ \mid\ m, n, p \geq 1\}$

\medskip
(e)
$L_{10} = \{xcy \ \mid\ |x| = 2|y|,\, x, y\in \{a, b\}^*\}$

\medskip
In each case, give a justification of the fact that
your grammar generates the desired language.

\vskip 0.25cm \noindent
{\bf Problem B5 (40 pts).} 
Given a context-free language $L$ and a regular language $R$, prove
that $L\cap R$ is context-free.

\medskip
{\bf Do not\/} use PDA's to solve this problem!

\medskip\noindent
{\it Hint\/}. Without loss of generality, assume
that $L = L(G)$, where $G = (V, \Sigma, P, S)$ is in Chomsky normal form,
and let $R = L(D)$, for some DFA $D = (Q, \Sigma, \delta, q_0, F)$.
Use a kind of cross-product construction
as sketched below. Construct a CFG $G_2$ whose set
of nonterminals is $Q\times N\times Q\ \cup\{S_0\}$,
where $S_0$ is a new nonterminal, and whose productions are
of the form:
%
$$S_0 \rightarrow (q_0, S, f),$$
for every $f\in F$;
$$(p, A, \delta(p, a)) \rightarrow a
\quad\hbox{iff}\quad
(A \rightarrow a) \in P,$$
for all $a\in \Sigma$, all $A\in N$,  and all $p\in Q$;
$$(p, A, s) \rightarrow (p, B, q)(q, C, s)
\quad\hbox{iff}\quad
(A \rightarrow BC)\in P,$$
for all $p, q, s\in Q$ and all $A, B, C\in N$;
$$S_0 \rightarrow \epsilon
 \quad\hbox{iff}\quad
(S\rightarrow \epsilon) \in P\ \hbox{and}\
q_0\in F.$$

\medskip
Prove that
for all $p, q\in Q$, all $A\in N$, all $w\in\Sigma^+$, and all $n\geq 1$,
$$(p, A, q) \lmder{n}_{G_{2}} w
\quad\hbox{iff}\quad
A \lmder{n}_{G} w\quad \hbox{and}\quad \delta^*(p, w) = q.$$
Conclude that $L(G_2) = L \cap R$. 


\vspace{0.5cm}\noindent
{\bf TOTAL: 330 points.}

\end{document}