\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
\renewcommand\emptyset\varnothing
\newcommand\Imp\Rightarrow
\renewcommand\hat\widehat
\newcommand\set[2]{\{#1\mid#2\}}
\newcommand\Iff\Leftrightarrow
\newcommand\Iffdef{\stackrel{\mathrm{def}}\Leftrightarrow}
\newcommand\goesto[2]{\underset{#2}{\overset{#1}\to}}
\newcommand\seq[3]{#1_{#2},\ldots,#1_{#3}}
\newcommand\subs\subseteq

%environment definitions

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

\begin{document}

\begin{center}
\framebox{\parbox\courseheader{\large Introduction to Theory of Computing\hfill Homework 7\\ 
CS 4810/5810 Spring 2025\hfill Due Friday, 28 March 2025}}
\end{center}
\medskip

\pagestyle{empty}

Do only question 1 (and 2 for 5810 students). The remaining questions are just some fun puzzles in case you need something to pass the time while lying on the beach next week.

\begin{enumerate}
\itemsep=1em
\item
Suppose you wanted to count the number of possible parse trees for a given string in a given grammar in Chomsky normal form. Describe how to modify the CKY algorithm to do this.

\item
(For 5810 students.)
Recall from class that CFLs are closed under union, concatenation, asterate, homomorphic image, and intersection with a regular set. Show that the CFLs are also closed under homomorphic preimage: If $L$ is a CFL and $h$ is a homomorphism, then $h^{-1}(L) = \set{x}{h(x)\in L}$ is also a CFL. (\emph{Hint}. Start with a grammar $G$ in Greibach normal form for $L\setminus\{\eps\}$. Build a new grammar $G'$ with the same nonterminals and productions $C\to aD_1\cdots D_k$ in $G'$ if $C\goesto*G h(a)D_1\cdots D_k$. Argue that the set of productions of $G'$ is finite. Then show by induction that for nonterminals $\seq C1k$, $\seq D1m$ and $x\in\Sigma^*$,
\begin{align*}
C_1\cdots C_k\goesto*{G'} xD_1\cdots D_m\ \Iff\ C_1\cdots C_k\goesto*G h(x)D_1\cdots D_m.
\end{align*}
Finally, if $\eps\in L$, figure out how to generate strings $x$ such that $h(x)=\eps$.)
\end{enumerate}

\hrulefill

\begin{enumerate}
\itemsep=1em
\setcounter{enumi}2
\item
\begin{enumerate}
\item
The \emph{postage stamp problem}: Prove that any amount of postage over 7 cents
can be made with some combination of 3 and 5 cent stamps.
\item
Prove that for any set $A\subs\{a\}^*$ whatsoever, $A^*$ is of the form $\set{a^{km}}{k\ge 0}\setminus F$, where $m$ is the greatest common divisor of the lengths of the nonnull strings in $A$ (or 0 if $A$ contains no nonnull strings) and $F$ is some finite set.
\end{enumerate}

\item
\begin{enumerate}
\item
Show that the set $\set{a^nb^{2n}}{n \geq 0}$ is a CFL.

\item
Show that the set $\set{a^{2^n}}{n\geq 0}$ is not a CFL.

\item
Using the set of 4(a) and the closure properties mentioned in 2, show how to express the set of 4(b) as a homomorphic image of the intersection of two CFLs.
\end{enumerate}
\end{enumerate}

\begin{center}
Enjoy your spring break!
\end{center}

\end{document}
