%
% Assignment 2c for CS3530 Computational Theory:
% Context-free Grammars and Pushdown Automata
% Fall 2024
%
% Problems taken from Sipser
%

\documentclass{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{ae,aecompl}
\usepackage{emp,ifpdf}
\usepackage{graphicx}
\usepackage{enumerate}

\ifpdf\DeclareGraphicsRule{*}{mps}{*}{}\fi

\empaddtoTeX{\usepackage{amsmath}}
\empprelude{input boxes; input theory}

% skip for paragraphs, don't indent
\parskip 6pt plus 1pt
\parindent=0pt
\raggedbottom

% a list environment with no bullets or numbers
\newenvironment{indentlist}{\begin{list}{}{\addtolength{\itemsep}{0.5\baselineskip}}}{\end{list}}

\begin{document}
\begin{empfile}

\begin{center}
\textbf{\Large CS 3530: Assignment 2c} \\[2mm]
Fall 2024
\end{center}

\raggedright


\section*{Exercise 2.6b (10 points)}

\subsection*{Problem}

Give context-free grammars generating the following languages.

\begin{enumerate}
\item[\textbf{b.}] The complement of the language $\{a^n b^n:n\geq 0\}$.

  Hint: The set of CFL
  is not closed under complement, so there is no generic operation to find the complement grammar.
  Examine the structure of strings in the complement language then create a grammar that will
  generate all of them.
\end{enumerate}

For all CFGs, describe the role that each rule performs as well as
giving the actual rule.

\subsection*{Solution}


\section*{Exercise 2.9(modified) (10 points)}

\subsection*{Problem}

In a previous assignment, you created a context-free grammar
that generates the language

$$
A=\{a^ib^jc^k|i=j\text{ or }j=k\text{ where }i,j,k\geq 0\}.
$$

Create a pushdown automaton that accepts strings from this
language by applying the construction algorithm from
Lemma 2.21 to your grammar. Only PDAs that follow this
construction will be accepted as solutions.

\subsection*{Solution}

\end{empfile}
\immediate\write18{mpost -tex=latex \jobname}
\end{document}
