<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[10pt]{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}}
\newcommand\sort{\mathop{\mathsf{sort}}}
\newcommand\perm{\mathop{\mathsf{perm}}}
\newcommand\subs\subseteq
\newcommand\eqdef{\stackrel{\mathrm{def}}\to}
\newcommand\len[1]{|#1|}

%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}

\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 &amp;\to aB \mid bA &amp;
A &amp;\to aS \mid bAA \mid a &amp;
B &amp;\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 &amp;\goesto{*}G x\ \ \Iff\ \ \#a(x) = \#b(x) &amp;
A &amp;\goesto{*}G x\ \ \Iff\ \ ??? &amp;
B &amp;\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 &amp;\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}

\item (For 5810 students.)
Let $\Sigma$ be a finite alphabet linearly ordered by $&lt;$. For a string $x\in\Sigma^*$, let $\sort x$ denote the string obtained by sorting the letters in $x$ in increasing order with respect to $&lt;$. For example, if $a &lt; b &lt; c$, then $\sort{baacacba} = aaaabbcc$. For $A\subs\Sigma^*$, let $\sort A \eqdef \set{\sort x}{x\in A}$. For example, if $A = \{ba,bab,bbbaa\}$ and $a &lt; b$, then $\sort A = \{ab,abb,aabbb\}$.

\emph{Parikh's theorem} \cite{Parikh66} states:

\medskip

\textbf{Theorem}\quad
For every context-free language $A$, there is a regular language $B$ such that $\sort B=\sort A$.

\medskip

Thus one cannot distinguish between CFLs and regular sets just by counting letters. Pilling \cite{Pilling73} gives a proof of Parikh's theorem with an explicit form (called Pilling normal form) for the regular set $B$:

\medskip

\textbf{Theorem}\quad
For every CFL $A$, there is a regular expression $e$ such that $\sort(L(e)) = \sort A$ and $e$ is a finite sum of expressions of the form $xy_1^* y_2^*\cdots y_k^*$, where $x,y_1,\ldots,y_k\in\Sigma^*$.

\medskip

Consider the two statements
\begin{enumerate}[(i)]
\item
For any $A\subs\Sigma^*$, if $A$ is regular, then so is $\sort A$.
\item
For any $A\subs\Sigma^*$, if $A$ is context-free, then so is $\sort A$.
\end{enumerate}
Both statements are trivially true for $\len\Sigma=1$, since in that case $\sort A=A$.
\begin{enumerate}
\item
Show that (i) is false for $\len\Sigma\geq 2$ and (ii) is false for $\len\Sigma\geq 3$.
\item
Show that (ii) is true for $\len\Sigma=2$. You may use the results of Parikh and Pilling cited above without proof.
\end{enumerate}
\end{enumerate}


\begin{thebibliography}{0}

\bibitem{Parikh66}
R.~J. Parikh.
\newblock On context-free languages.
\newblock {\em J. Assoc. Comput. Mach.}, 13(4):570--581, 1966.

\bibitem{Pilling73}
D.~L. Pilling.
\newblock Commutative regular equations and {P}arikh's theorem.
\newblock {\em J. London Math. Soc.}, 6(4):663--666, June 1973.

\end{thebibliography}

\end{document}
</pre></body></html>