\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\Res{{\rm Res}}
\def\buildrell#1\over#2{\mathrel{\mathop{\null#1}\limits_{#2}}}
\def\der#1{\buildrel #1\over\Longrightarrow}

%
\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}
Final Exam}\\[10pt]
{\large May 5, 2009\\[10pt]
Note that this is an {\bf open-book exam\/} \\
{\bf Read\/} all the questions {\bf before\/} starting
solving any of them!}
\end{center}


\vspace{0.25cm}\noindent
{\bf Problem 1 (15 pts).} 
Given any regular expression, $S$, over $\Sigma$,
define $S^R$ recursively as follows:
\begin{eqnarray*}
a_i^R & = & a_i \\
\epsilon^R & = & \epsilon \\
\emptyset^R & = & \emptyset \\
(S_1 + S_2)^R & = & (S_1^R + S_2^R) \\ 
(S_1 \cdot S_2)^R & = & (S_2^R \cdot S_1^R) \\
(S_1^*)^R & = & (S_1^R)^*. 
\end{eqnarray*}

Prove that
\[
\s{L}[S^R] = (\s{L}[S])^R,
\]
where $(\s{L}[S])^R$ denotes the reversal of the language $\s{L}[S]$,
that is, \\
$(\s{L}[S])^R = \{w^R\in \Sigma^* \mid w\in \s{L}[S]\}$.
You may use without proof the fact that
\[
(uv)^R = v^Ru^R,
\]
for any two strings, $u, v$.

\medskip
(Recall, $\s{L}[S]$ is the regular language denoted by the regular
expression $S$.)


\vspace{0.25cm}\noindent
{\bf Problem 2 (20 pts).} 
Let $\Sigma$ be an alphabet. Recall that a binary relation,
$\sim$, on $\Sigma^*$,  is {\it left invariant\/}
iff $u\sim v$ implies that $wu\sim wv$ for all $w \in \Sigma^{*}$
and  {\it right invariant\/} iff $u\sim v$ implies that
$uw\sim vw$ for all $w \in \Sigma^{*}$.
An equivalence relation on $\Sigma^*$ that is both left and
right-invariant is called a {\it congruence\/}.
Recall that a congruence satisfies the property:
If $u \sim u'$ and $v \sim v'$, then $uv \sim u'v'$
(You {\bf do not\/} have to prove this). 

\medskip
Given any regular language, $L$, over $\Sigma^*$ let
\[
L^{1/3} = \{w\in \Sigma^* \mid wcwdw \in L\},
\]
where $c, d \in \Sigma$ are some given letters. 
Prove that $L^{1/3}$ is also regular.


\vspace{0.25cm} \noindent
{\bf Problem 3 (25 pts).} 

Consider the language (over $\Sigma = \{a, b\}$) 
\[
L_1 = \{w\in \{a, b\}^* \mid \#(a) = \#(b)\}
\]
consisting of all strings having an equal number of  $a$'s and $b$'s
and  the language
\[
L_1' = \{w\in \{a, b\}^* \mid \#(b) > \#(a)\}
\]
consisting of all strings having strictly more $b$'s than $a$'s.


\medskip
(1) Prove that  every nonempty string $w\in L_1$ is of the
form
\begin{enumerate}
\item[(1)]
$w = aub$, where $u\in L_1$ ($u = \epsilon$ is allowed);
\item[(2)]
$w = bua$, where $u\in L_1$ ($u = \epsilon$ is allowed);
\item[(3)]
$w = uv$, where $u, v\in L_1$, with $u, v\not= \epsilon$. 
\end{enumerate}
and that  every nonempty string $w\in L_1'$ is of the
form
\begin{enumerate}
\item[(1)]
$w = bu$, where $u\in L_1\cup L_1'$
($u = \epsilon$ is allowed);
\item[(2)]
$w = uv$, where $u\in L_1$ and $v\in L_1'$, with $u\not= \epsilon$. 
\end{enumerate}

\medskip
(2) 
Using the above, give a context-free grammar for $L_1'$.

\vspace{0.25cm}
\noindent
{\bf Problem 4 (25 pts).} 
Prove that the following languages are not 
context-free:
\begin{eqnarray*}
L_1 & = & \{u\#v\#u\#v\mid u, v\in \{a, b, c, d\}^+\},\\
L_2 & = & \{a^{n^2}\mid n \geq 1\}.
\end{eqnarray*}

\medskip\noindent
{\it Hint\/}.
To prove  $L_1$ non context-free, 
you may want to consider the intersection of $L_1$ with
a well chosen regular language.

\vspace{0.25cm}
\noindent
{\bf Problem 5 (10 pts).} 
Let $\{\varphi_i\}$ be an acceptable indexing of the partial
recursive functions (over $\natnums$).
Prove that the following problems are undecidable:
\begin{enumerate}
\item[(1)]
$\varphi_i(0) = \varphi_a(0)$ and
$\varphi_i(1) = \varphi_a(1)$,
for some given partial recursive function, $\varphi_a$.
\item[(2)]
$\varphi_i(0) = \varphi_j(0)$ and
$\varphi_i(1) = \varphi_j(1)$,
for any two partial recursive functions, $\varphi_i$ and $\varphi_j$.
\end{enumerate}

\vspace{0.25cm}
\noindent
{\bf Problem 6 (25 pts).} 
(i)
Given any context-free language, $L\subseteq \{a, b\}^*$, 
is the following problem decidable:

\medskip
$L \subseteq a^*b^*$?

\medskip
(ii)
If $R \subseteq \{a\}^*$ is a regular language
and $L\subseteq \Sigma^*$ is any context-free language,
with $a\in \Sigma$, is it decidable whether
\[
R \subseteq L\hbox{?}
\]
What if $R$ is any regular language (not necessarily over
the alphabet $\{a\}$)?
\end{document}