%
% Assignment 2g for CS3530 Computational Theory:
% Context-free Languages
% Fall 2023
%
% 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 2g} \\[2mm]
Fall 2023
\end{center}

\raggedright

\section*{Problem 2.30d (10 points)}

\subsection*{Problem}

Use the pumping lemma to show that the following languages are not context free.

\begin{itemize}
\item [d.] $\{ t_1\#t_2\# \cdots \#t_k | k \ge 2, $ each $ t_i \in \{a,b\}^*$, and $t_i = t_j$ for some $i \ne j \}$

  \textbf{Solution}
  
\end{itemize}
\section*{Problem 2.31 (10 points)}

\subsection*{Problem}

Let $B$ be the language of all palindromes over $\{0,1\}$ containing
an equal number of $0$s and $1$s. Show that $B$ is not context free.

\subsection*{Solution}

\end{document}
