\documentclass[12pt]{article}
\usepackage{amsfonts,amsmath,amssymb}
\usepackage{fullpage}
\usepackage[left=1.0in,top=1.0in,right=1.0in,bottom=1.25in]{geometry}
\usepackage{bbold}
\usepackage{parskip}
\usepackage{tikz}
\usetikzlibrary{topaths,calc,automata,positioning}
\pagenumbering{gobble}


\setlength{\arraycolsep}{4pt}

\begin{document}
\begin{center}
\section*{CS 360 --- Introduction to the Theory of Computing \\ Assignment 3}
\subsection*{University of Waterloo, Spring 2018}
\end{center}
{\it Due 5:00 PM, June 15, 2018.}

\begin{enumerate}
\item Consider the following context-free grammar $G$:
\begin{align*}
S &\to ABA \\
A &\to aA \mid \varepsilon \\
B &\to bB \mid \varepsilon
\end{align*}
\begin{enumerate}
\item Give a parse tree for the word abaa.
\item Show that $G$ is ambiguous.
\item What is the language that $G$ generates? Briefly explain how $G$ generates this language (no formal proof necessary).
\end{enumerate}

\item Consider the following context-free grammar $G$:
\begin{equation*}
S \to aSa \mid bSb \mid \$
\end{equation*}
\begin{enumerate}
\item What is the language that $G$ generates? Show this via induction.
\item Give the equivalent grammar in Chomsky normal form.
\end{enumerate}

\item Consider the following pushdown automaton $A$:
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[shorten >=1pt,on grid,node distance=3cm,>=stealth,thick,auto]
    \node[state,initial] (0) {$q_0$};
    \node[state] (1) [right of=0]{$q_1$};
    \node[state] (2) [right of=1]{$q_2$};
    \node[state,accepting] (3) [right of=2]{$q_3$};
    \path[->]
        (0) edge [loop above] node [align=left] {$a,Z_0/XZ_0$ \\ $a,X/XX$} (0)
        (1) edge [loop above] node [align=left] {$b,X/\varepsilon$ \\ $b,Z_0/YZ_0$ \\ $b,Y/YY$} (1)
        (2) edge [loop above] node [align=left] {$c,Y/\varepsilon$} (2)
        (0) edge node [align=left] {$\varepsilon,Z_0/Z_0$ \\ $b,X/\varepsilon$} (1)
        (1) edge node [align=left] {$\varepsilon,Z_0/Z_0$ \\ $c,Y/\varepsilon$} (2)
        (2) edge node {$\varepsilon,Z_0/Z_0$} (3)
        ;
\end{tikzpicture}
\end{center}
\end{figure}
\begin{enumerate}
\item What language does $A$ recognize? Briefly explain how $A$ recognizes this language.
\item Give a context-free grammar that recognizes the same language. No proof is necessary, though you may wish to give a brief explanation to help convince the reader it is correct.
\end{enumerate}


\item Suppose a language $L \subseteq \Sigma^*$ is accepted by a PDA by final state and the PDA has the property that for any word $w \in \Sigma^*$, the stack of the PDA on input $w$ never has more than $3$ elements of $\Gamma$ on it. Prove that $L$ is regular.

\item Let $L = \{ w \in \{a,b,c,d\}^* \mid |w|_a = |w|_d \wedge |w|_b = |w|_c \}$. Show that $L$ is not context-free.

\end{enumerate}
\end{document}
