\documentclass{article}[11pt]
\begin{document}

\centerline{CSCI 2400 -- Models of Computation, Section 3}
\vspace{0.5cm}
\centerline{\Large Practice Final Exam}
\vspace{0.5cm}

\vspace{0.5cm}
\noindent
{\bf 1.}
Prove that the following language is not context-free.
$$L= \{a^ib^jc^k: 0 \leq i \leq j \leq k \}$$

\vspace{0.5cm}
\noindent
{\bf 2.}
Prove that the following language is context-free.
$$L = \{ww^R: w \neq abba, ~ \mbox{and}~ w \in \{a,b\}^* \}$$

\vspace{0.5cm}
\noindent
{\bf 3.}
Design a Turing Machine that accepts the following language.
$$L = \{ ab(a+b)^* \} $$


\vspace{0.5cm}
\noindent
{\bf 4.}
Describe the algorithm of a three-tape 
Turing machine that computes the following function.
$$f(x) = x^2$$

\vspace{0.5cm}
\noindent
{\bf 5.}
Show that the class of Pushdown Automata with two stacks
are equivalent with the Turing machines.

\vspace{0.5cm}
\noindent
{\bf 6.}
Describe a procedure that enumerates the following strings
in proper order.
$$S = \{ 1^{2^n} : n \geq 0 \} $$

\vspace{0.5cm}
\noindent
{\bf 7.}
Prove that the family of recursively enumerable languages
is closed under union.

\vspace{0.5cm}
\noindent
{\bf 8.}
Prove that family of recursive languages 
are closed under intersection.

\vspace{0.5cm}
\noindent
{\bf 9.}
Prove that the problem of determining
whether $w \in L(G)$, where $G$ is a context-free
grammar, is decidable.

\vspace{0.5cm}
\noindent
{\bf 10.}
Prove that the problem of determining whether two 
Turing machines accept the same language is undecidable.

\end{document}








































































