\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, 2004 \hspace*{0.4cm} CIS 511}}\\
\vspace{1cm}
{\Large\bf Introduction to the Theory of Computation\\
Jean Gallier \\
\vspace{0.5cm}
Homework 4}\\[10pt]
March 4, 2004; Due March 25, 2004\\
\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 (40 pts).} 
The purpose of this problem is to get a fast
algorithm for testing state equivalence in a DFA.
Let $D=(Q,\Sigma,\delta,q_{0},F)$ be a deterministic finite
automaton. Recall that {\it state equivalence\/} is the equivalence
relation $\equiv$ on $Q$, defined  such that,
$$p \equiv q\quad \hbox{iff}\quad \forall z\in\Sigma^* 
(\delta^{*}(p,z) \in F\quad \hbox{iff}\quad \delta^{*}(q,z) \in F).$$
and that {\it $i$-equivalence\/} is the equivalence
relation $\equiv_{i}$ on $Q$, defined such that,
$$p \equiv_{i} q\quad \hbox{iff}\quad \forall z\in\Sigma^*,\ |z| \leq i\ 
(\delta^{*}(p,z) \in F\quad \hbox{iff}\quad \delta^{*}(q,z) \in F).$$

\medskip
A relation $S\subseteq Q\times Q$ is a {\it forward closure\/} iff 
it is an equivalence relation and
whenever $(p, q)\in S$, then $(\delta(p, a), \delta(q, a))\in S$,
for all $a\in\Sigma$.

\medskip
We say that a forward closure $S$ is {\it good\/} iff 
whenever $(p, q)\in S$, then $good(p, q)$, where 
$good(p, q)$ holds iff either both $p, q\in F$, or
both $p, q\notin F$.

\medskip
Given any relation $R\subseteq Q\times Q$,
recall that the smallest equivalence relation $R_\approx$ containing
$R$ is the relation $(R \cup R^{-1})^*$
(where $R^{-1} = \{(q, p)\ \mid\ (p, q)\in R\}$, and 
$(R \cup R^{-1})^*$ is the reflexive and transitive closure of 
$(R \cup R^{-1})$).
We define the sequence of relations $R_i\subseteq Q\times Q$
as follows:

$$\eqaligneno{
R_0 &= R_{\approx}\cr
R_{i + 1} &= (R_{i} \cup 
\{(\delta(p, a), \delta(q, a))\ \mid\ (p, q)\in R_i,\ a\in \Sigma\})_{\approx}.
}$$

\medskip
(i) Prove that $R_{i_{0}+1} = R_{i_{0}}$ for some least $i_0$.
Prove that $R_{i_{0}}$ is the smallest forward closure
containing $R$.
 
\medskip
We denote the smallest forward closure $R_{i_{0}}$ containing $R$ as
$R^{\dagger}$, and call it the
{\it forward closure of $R$\/}.

\medskip
(ii) Prove that $p\equiv q$ iff the forward closure $R^{\dagger}$ of the
relation $R = \{(p, q)\}$ is good.


\vspace{0.25cm}\noindent
{\bf Problem B3 (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 B4 (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.25cm}\noindent
{\bf Problem B5 (40 pts).} 
Give context-free grammars for the languages
\begin{eqnarray*}
L_1 & = & \{xcy\ \mid \ x\not= y,\, x, y\in \{a, b\}^*\}\\
L_2 & = & \{xcy\ \mid\ \ x\not= y^R,\, x, y\in \{a, b\}^*\}.
\end{eqnarray*}


\vspace {0.25cm}
\noindent
{\bf Problem B6 (50 pts).} 
Let $L\subseteq \{a\}^*$ be a context-free language.
Prove that $L$ is actually a regular language.
Proceed as follows.
If $L$ is finite, this is obvious, thus, assume that
$L$ is infinite. Let $L = L(G)$, for some CFG $G$.

\medskip
(i)
Let $K > 1$ be the constant of the pumping lemma for $G$,
and let $r = K!$.
Prove the following fact: for every $w\in L$, if $|w| \geq K$, then
$$\{w a^{rn} \ \mid\ n \geq 0\} \subseteq L.$$

\medskip
(ii) For every $i$ such that $0 \leq i < r$, let
$$L_i = \{a^n \ \mid\ a^n\in L,\, n \geq K,\, n \equiv i \bmod r\}.$$
Clearly, 
$$L = \{a^n \ \mid\ a^n \in L,\, n < K\}
\cup \bigcup_{i = 0}^{r-1} L_i.$$
If $L_i\not=\emptyset$, let $z_i$ be the shortest string in $L_i$.
Prove that
$$L_i = \{z_i a^{rm}\ \mid \ m \geq 0\}.$$
Conclude that $L$ is regular.

\medskip
(iii)
Prove that it is decidable whether $L_i = \emptyset$
(i.e., describe (concisely) an algorithm).

\medskip
(iv)
Given a context-free language $L$ over $\{a, b\}$, prove that it is decidable
whether \\
$\{a\}^* \subseteq L$
(i.e., describe (concisely) an algorithm).


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

\end{document}