\documentclass{article}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{fullpage}
\usepackage{eucal}
\usepackage{graphicx}
\usepackage{color}
\usepackage{tikz}
\usepackage{algorithm,algorithmic}

\newcommand{\e}{\varepsilon}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\question}[1]{\vspace{10pt}\noindent $\mathbf{#1}$}
\newcommand{\yieldstar}{\stackrel{*}{\Rightarrow}}
\newcommand{\yields}{\Rightarrow}

\newtheorem{objective}{Objective}

\begin{document}
  
  \begin{minipage}{\textwidth}
    CSE3502 - Theory of Computation \hfill \today\\
    \textbf{Due: Before class on March 25, 2014}\\
    \\
    \centering{Homework 5} \hfill
  \end{minipage}

  \input{hw_survey}
  
  \section{The Pumping Lemma for CFLs} % (fold)
  
    \question{1}
    Let $A$ and $B$ be languages over $\Sigma=\{0,1\}$ defined as
    \begin{align*}
      A &= \{(0\cup 1)^a (1\cup 2)^b (2\cup 3)^c \mid a\ge b \}, \text{ and}\\
      B &= \{(0\cup 1)^a (1\cup 2)^b (2\cup 3)^c \mid a = c \}.
    \end{align*}
    \begin{itemize}
      \item Prove that $A$ and $B$ are context-free.
      \item Prove that $A\cup B$ is context free.  \textbf{Think about this:} Would your proof work for any pair of CFLs?
      \item Prove that $A\cap B$ is not context free.  This implies that the context-free languages are not closed under intersection.
      \item It is a basic fact in set theory that $\overline{X\cup Y} = \overline{X}\cap \overline{Y}$.  Use the previous problems to show that the class of conext-free languages are not closed under the complement operation.
    \end{itemize}
  
  % section the_pumping_lemma (end)

  \section{Turing Machines} % (fold)

    \question{2}
    Give Turing Machines for the languages $A$, $B$, $A\cup B$, and $A\cap B$ from question $1$.
    Indicate the transition functions by drawing the state diagram.
  
  % section turing_machines (end)

\end{document}