\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 Summer 1, 2006 \hspace*{0.4cm} CIS 511}}\\
\vspace{1cm}
{\Large\bf Introduction to the Theory of Computation\\
Jean Gallier \\
\vspace{0.5cm}
Homework 3}\\[10pt]
June 6, 2006; Due June 15, 2006\\
\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 {1cm}
``B problems'' must be turned in.

\vspace{0.25cm}\noindent
{\bf Problem B1 (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)\ |\ (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))\ |\ (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 B2 (30 pts).} 
(i)
A context-free grammar $G = (V, \Sigma, P, S)$
is called an {\it extended right-linear grammar\/} iff its
productions are of the form
\begin{eqnarray*}
A & \longrightarrow & \alpha B \\
A & \longrightarrow & w
\end{eqnarray*}
where $A, B\in N = V - \Sigma$, $\alpha\in \Sigma^*$,
and $w\in \Sigma^*$.
Note that chain rules $A \longrightarrow B$ are allowed
as well as $\epsilon$-rules $A \longrightarrow \epsilon$.

\medskip 
(i)
Prove that a language is regular iff it is generated
by an extended right-linear grammar.

\medskip
(ii)
A context-free grammar $G = (V, \Sigma, P, S)$
is called an {\it extended left-linear grammar\/} iff its
productions are of the form
\begin{eqnarray*}
A & \longrightarrow & B \alpha  \\
A & \longrightarrow & w
\end{eqnarray*}
where $A, B\in N = V - \Sigma$, $\alpha\in \Sigma^*$,
and $w\in \Sigma^*$.
Note that chain rules $A \longrightarrow B$ are allowed
as well as $\epsilon$-rules $A \longrightarrow \epsilon$.

\medskip 
Prove that a language is regular iff it is generated
by an extended left-linear grammar.

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

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

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

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

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

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

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

\medskip
(e)
$L_{10} = \{xcy \ |\ |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.5cm}\noindent
{\bf TOTAL:  210 points.}

\end{document}