\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 Practice Midterm Exam}
\vspace{0.5cm}

\vspace{0.5cm}
\noindent
{\bf 1.} (15 points)
Give an NFA with a single final state
for the following regular language:
$$aa^*b^*a \cup aab^*$$

\vspace{0.5cm}
\noindent
{\bf 2.} (10 points)
Give the regular expression for the following
regular language over the alphabet $\Sigma = \{0,1\}$:

\begin{eqnarray*}
L & = &  \mbox{\{the binary positive integers (without 0)} \\
  &&     \mbox{~~whose most significant bit is 1} \\
  &&    \mbox{~~and contain the substring $11$\}}
\end{eqnarray*}

\vspace{0.5cm}
\noindent
{\bf 3.} (15 points)
Use the pumping lemma to prove that the following language
is not regular:
$$\{a^nb^kc^n ~~:~ n \geq 0, ~ k \geq 5\}$$

\vspace{0.5cm}
\noindent
{\bf 4.} (15 points)
Give the NPDA for the following context-free language,
describe what each state does:

$$\{a^nb^k~~:~ n > k \geq 0\}$$

\vspace{0.5cm}
\noindent
{\bf 5.} (15 points)
(a) Give a context-free grammar for the following language:

$$L = \{wa^nb^nw^R~~:~n \geq 0\}$$

where $w$ is any string over the alphabet $\Sigma = \{ a, b\}$
including $\lambda$.

(b) Give the derivation of the string $abaabbba$ using
your grammar.

\vspace{0.5cm}
\noindent
{\bf 6.} (15 points)
Is the following grammar ambiguous? Prove your answer.

\begin{eqnarray*}
&& S \to BA ~|~ C \\
&& B \to Bb ~|~ b \\
&& A \to aA ~|~ a \\
&& C \to bCa ~|~ ba
\end{eqnarray*}


\vspace{0.5cm}
\noindent
{\bf 7.} (15 points)
Give the Chomsky normal form of the following grammar.
\begin{eqnarray*}
&& S \to AbBa \\
&& A \to ABa ~|~ a \\
&& B \to BaA ~|~ b
\end{eqnarray*}

\end{document}








































































