\documentclass[11pt]{article}
\usepackage[letterpaper,margin=1in]{geometry}
\usepackage{amsmath,amsthm,amssymb,latexsym}
\usepackage{array,multirow,alltt,enumerate,bbm,eucal,graphicx}
\usepackage[colorlinks]{hyperref}
\usepackage{xcolor,stmaryrd,bussproofs,mathpartir}
\usepackage{tikz,pgfmath}
\usepgflibrary{shapes}
\usetikzlibrary{arrows,automata,backgrounds}

\setlength\parindent{0in}
\addtolength\parskip{1ex}
\setlength\fboxrule{.5mm}\setlength{\fboxsep}{1.2mm}
\newlength\courseheader
\courseheader=\textwidth
\addtolength\courseheader{-4mm}
\parindent=0pt
\parskip=1ex

%macro definitions

\newcommand\eps{\varepsilon}
\newcommand\Imp{\Rightarrow}
\renewcommand\hat{\widehat}
\newcommand\set[2]{\{#1\mid#2\}}
\newcommand\Iff\Leftrightarrow
\newcommand\Iffdef{\stackrel{\mathrm{def}}\Leftrightarrow}
\newcommand\rev{\mathop{\mathsf{rev}}}
\newcommand\floor[1]{\lfloor#1\rfloor}
\newcommand\goesto[2]{\underset{#2}{\overset{#1}\to}}

%environment definitions

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\begin{document}

\begin{center}
\framebox{\parbox\courseheader{\large Introduction to Theory of Computing\hfill Homework 6\\ 
CS 4810 Spring 2022\hfill Due Tuesday, 15 March 2022}}
\end{center}
\medskip

\pagestyle{empty}

\noindent
Our first and only prelim is scheduled for \textbf{Thursday, March 24}. The exam will be in class during the regular lecture period, 75 minutes, open book and notes. You will be responsible for all material covered in class up through and including the 3/17 lecture, with the exception of the material from the 2/17 and 2/22 lectures on automata as coalgebras, which will not be tested.

\hrulefill

\begin{enumerate}
\item
Prove that the following CFG $G$ in Greibach normal form generates
exactly the set of nonnull strings over $\{a,b\}$ with equally many $a$'s
and $b$'s:
\begin{align*}
S &\to aB \mid bA &
A &\to aS \mid bAA \mid a &
B &\to bS \mid aBB \mid b
\end{align*}
(\emph{Hint}: Strengthen your induction hypothesis to describe the sets of
strings generated by the nonterminals $A$ and $B$: For $x\ne\eps$,
\begin{align*}
S &\goesto{*}G x\ \ \Iff\ \ \#a(x) = \#b(x) &
A &\goesto{*}G x\ \ \Iff\ \ ??? &
B &\goesto{*}G x\ \ \Iff\ \ ???\ \ )
\end{align*}

\item
Here is a CFG for the set $\mathrm{PAREN}_2$ of balanced strings of parentheses of two types, \texttt{(} \texttt{)} and \texttt{[} \texttt{]}.
\begin{align*}
S &\to \texttt{(}\,S\,\texttt{)} \mid \texttt{[}\,S\,\texttt{]} \mid SS \mid \eps
\end{align*}
For example, \texttt{(\,[\,(\,)\,[\,]\,]\,(\,[\,]\,)\,)} is in $\mathrm{PAREN}_2$, but \texttt{[\,(\,]\,)} is not.
Give CFGs in (a) Chomsky and (b) Greibach normal form generating the set $\mathrm{PAREN}_2-\{\eps\}$.

\item
Let $b(n)$ denote the binary representation of $n\ge 1$, leading zeros omitted. For example, $b(5) = 101$ and $b(12) = 1100$. Let \# be another symbol not in $\{0,1\}$.
\begin{enumerate}
\item
Show that the set $\set{b(n)\#b(n+1)}{n\ge 1}$ is not a CFL.
\item
Suppose we reverse the first numeral; that is, consider the set $\set{\rev{b(n)}\#b(n+1)}{n\ge 1}$. Show that this set is a CFL.
\end{enumerate}
\end{enumerate}

\end{document}
