\documentclass{article}[11pt]
\usepackage{epsfig}


\newcommand{\postscript}[2]
 {\setlength{\epsfxsize}{#2\hsize}
  \centerline{\epsfbox{#1}}}

\begin{document}

\centerline{CSCI 2400 -- Models of Computation, Section 3}
\vspace{0.5cm}
\centerline{\Large Homework 4}
\vspace{0.5cm}
\centerline{Return by: Thursday, October 12} 

\vspace{0.5cm}
\noindent
{\bf 1.}
Use the pumping lemma to prove that the following languages
are not regular. (The alhabet is $\Sigma = \{ a, b \}$.)
\begin{itemize}
\item[(a)]
$L = \{ a^nb^la^k: k \geq n+l \}$
\item[(b)]
$L = \{ ww: w \in \Sigma^* \}$
\item[(c)]
$L = \{ a^{k^2} \}$
\item[(d)]
$L = \{uww^Rv: u,v,w \in \Sigma^+, |u| \geq |v|\}$
\end{itemize}

\vspace{0.5cm}
\noindent
{\bf 2.}
Which of the following languages are regular? Give short explanations.
(The alphabet is $\Sigma = \{ a, b \}$.)
\begin{itemize}
\item[(a)]
$L = \{w: n_a(w) \neq n_b(w) \}$
\item[(b)]
$L = \{a^nb^l: n \geq 100, l \leq 100\}$
\item[(c)]
$L = \{uww^Rv: u,v,w \in \Sigma^+\}$
\item[(d)]
$L = \{b^n a^l b^k: n > 5, l > 3, l \geq k \}$ 
\end{itemize}
	
\vspace{0.5cm}
\noindent
{\bf 3.}
Find context-free grammars for the following languages.
Explain your answers.
\begin{itemize}
\item[(a)]
$L = \{ w:~\mbox{$w$ starts and ends with the same symbol,
         and $w \in \{a, b\}^*$} \}$
\item[(b)]
The complement of the language $L = \{ a^nb^n \}$.
\item[(c)]
$L = \{w : n_a(w) = 2 n_b(w), 
           \mbox{where $w \in \{a,b\}^*$}\}$
\item[(d)]
$L = \{w\#x: 
       \mbox{$w^R$ is a substring of x, 
       where $w, x \in\{a,b\}^*$}\}$  

\end{itemize}

\vspace{0.5cm}
\noindent
{\bf 4.}
You are given the following ambiguous context-free grammar:
\begin{eqnarray*}
S & \rightarrow & AB|aaB \\
A & \rightarrow & a | Aa \\
B & \rightarrow & b
\end{eqnarray*}
\begin{itemize}
\item[(a)]
Find a string $s$ 
generated by the grammar that has two leftmost derivations.
Show the derivations.
\item[(b)]
Show the two derivation trees for the string $s$.
\item[(c)]
Find an equivalent unambiguous context-free grammar.
Explain your answer.
\item[(d)]
Give the unique leftmost derivation and derivation tree for the string $s$
generated from the unambiguous grammar of part (c).
\end{itemize}
\end{document}








































































