%
% Assignment 2d for CS3530 Computational Theory:
% Context-free Languages
% 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{enumerate}

% 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{center}
\textbf{\Large CS 3530: Assignment 2d} \\[2mm]
Fall 2024
\end{center}

\raggedright


\section*{Example 2.18 (10 points)}

\subsection*{Problem}

The example from the book creates a PDA for the language $\{ ww^R | w \in \{0,1\}^* \}$.
Figure 2.19 shows the PDA diagram.  Use the grammar construction from Lemma 2.27 to
construct a context-free grammar for this language.  Only the grammar created from
this construction process will be allowed for credit.

\subsection*{Solution}


\section*{Problem 2.23 (10 points)}

\subsection*{Problem}

Let $D=\{xy: x,y \in \{0,1\}^*$ and $|x|=|y|$ but $x \neq y\}$. Show
that $D$ is a context-free language.

Hint: How do we show that a language is context-free?

\subsection*{Solution}

\end{document}
