\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 6}
\vspace{0.5cm}
\centerline{Return by: Monday, November 6} 

\vspace{0.5cm}
\noindent
{\bf 1.} (40 points)
Use the pumping lemma to prove that the following languages
are not context-free.
\begin{itemize}
\item[(a)]
$L = \{ a^n: \mbox{ $n$ is prime} \}$
(A prime number is divided only by itself and 1.)
\item[(b)]
$L = \{ a^nb^j: n \leq j^2 \}$
\item[(c)]
$L = \{ a^nb^jc^k: k = jn \}$
\item[(d)]
$L = \{w: n_a(w) < n_b(w) < n_c(w)\}$
\end{itemize}

\vspace{0.5cm}
\noindent
{\bf 2.} (15 points)
Which of the following languages are context-free? Give short explanations.
\begin{itemize}
\item[(a)]
$L = \{a^nww^Ra^n: n \geq 0, w \in \{a,b\}^*  \}$
\item[(b)]
$L = \{a^nb^ja^nb^j: n,j \geq 0 \}$
\item[(c)]
$L = \{a^nb^ja^jb^n: n,j \geq 0 \}$
\item[(d)]
$L = \{a^nb^nc^j: n \leq j\}$ 
\end{itemize}
        
\vspace{0.5cm}
\noindent
{\bf 3.} (15 points)
Problem 4, page 227.

\vspace{0.5cm}
\noindent
{\bf 4.} (15 points)
Problem 17, page 227.

\vspace{0.5cm}
\noindent
{\bf 5.} (15 points)
Problem 2, page 244.

\end{document}








































































