\documentclass{article}
\usepackage{graphics}
\usepackage{fancyhdr}
\usepackage{amsmath}
\usepackage[topbottom,singlearrows]{logicsym}
\usepackage{multicol}

\newcommand{\coursenumber}{081}
\newcommand{\coursetitle}{Computability and Logic}

\topmargin  18pt  	% 27pt
\headheight 12pt  	% 12pt
\headsep    35pt 	% 45pt
\textheight 8.0in
\textwidth  6.2in

\oddsidemargin   22pt      % Left margin on odd-numbered pages.
\evensidemargin  22pt      % Left margin on even-numbered pages.
\marginparwidth  72pt       % Width of marginal notes.
\marginparsep    11pt      % Horizontal space between outer margin and 
                           % marginal note

\pagestyle{fancy}
\lhead{CSCI \coursenumber}
\chead{}
\rhead{\semester}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
\newcommand{\semester}[0]{
     \ifnum\month>7{Fall}\fi
     \ifnum\month<8{Spring}\fi\  \number\year
}

\begin{document}

\begin{center}{\Large Homework 5}\\ \vspace{1 ex} Due midnight,
Thursday, 2/26/2015 \end{center}

\vspace{2 ex}
\noindent

Please submit your homework solutions online at  
\texttt{http://www.dci.pomona.edu/tools-bin/cs081upload.php}.  If you 
have more than one file to be turned in, please put it in a folder 
and zip it up before turning it in.

Problems from the texts are given in the form c.n where c is the 
chapter and n is the problem number.  Thus problem 2.7 is problem 7 
from Chapter 2.

\vspace{2 ex}

\begin{enumerate}
    
    \item (15 points)  \textbf{CFL's over alphabet of size 1}
    \begin{enumerate}
	\item Let $L$ be a context-free language over the one-element
	alphabet $\{a\}$.  Show that $L$ is regular.  
	
	Hint: Let $p$ be the
	constant from the Pumping Lemma.  Show that for each $x \in L$
	with $p \leq |x|$, there are natural numbers
	$r$ and $s$,with $s$ no greater than $p$, such that the set 
	$A_{r,s} = \{a^{r+is} | 0 \leq i \}$ is a
	subset of $L$. Then show that $L$ is the union of a (possibly
	empty) finite set of strings of length less than $p$ together
	with finitely many sets of the form $A_{r,s}$ (and note that 
	$A_{r,s}$ is regular).

	\item Prove that the set $\{a^{n} | n\textrm{ is a prime 
	number}\}$ is not context-free.  \emph{Hint:  Use the first 
	part to make your life simpler.}
    \end{enumerate}
	
    \item (5 points)  \textbf{Closure}
    
    Rich 13.19.  Hint:  Use L = $\{1a^{n}b^{2n} \cup 2a^{n}b^{n} | n 
    \ge 0\}$
    
    \item (5 points)  \textbf{Algorithms}
    
    Rich 14.1d.
    
    \item (10 points) \textbf{Parsing with CKY}
    
    Consider the Chomsky Normal Form grammar $S \rightarrow AB$, $A
    \rightarrow a$, and $B \rightarrow AB\ |\ b$.  Use the CKY
    algorithm to fill in a table like the one in class for each of the
    strings $aab$ and $aba$.  Use these tables to determine if each 
    of the strings is in the language generated by the grammar.  If 
    they are, explain how to use the table to produce a derivation.
    
    \item (20 points) \textbf{Unique Readability}
    
    For this problem consider formulas of propositional logic to be
    exactly those generated by the grammar given in class (and thus
    only those formulas that are fully parenthesized.)  Consider the
    following function on symbols from the alphabet $\mathcal{A}$ of
    propositional logic.  \newlength{\pwidth}
    \settowidth{\pwidth}{$p$}

    $\begin{array}{l}
    K(\mbox{\hbox to\pwidth{\hss\textrm(\hss}}) = -2 \\
    K(\mbox{\hbox to\pwidth{\hss\textrm)\hss}}) = 2 \\
    K(p)      = 1\mbox{, for a proposition letter $p$} \\
    K(\top)      = K(\bot) = 1 \\
    K({\neg})     = 0 \\
    K({\And})     = K({\Or}) = K({\Implies}) = -1
    \end{array}$
    
    We extend the function to strings of symbols,
    $K^{*}:\mathcal{A}^{*}\rightarrow N$ in the natural way:
    $K^{*}(\epsilon)=0$ and $K^{*}({a}s)=K({a})+K^{*}(s)$.  You may
    use without proof the fact that $K^{*}(st)=K^{*}(s)+K^{*}(t)$.

    \begin{enumerate}
	\item Prove by induction that if $\phi$ is a formula of
	propositional logic, then $K^{*}(\phi)=1$.

	
	\item
	A string $s$ is a \emph{proper prefix} of a formula $u$ if
	there is a non-empty string $t$ such that $st=u$.  Prove that
	$K^{*}(s)<1$ for any string $s$ which is a proper prefix of
	some formula.


	\item Conclude that a formula cannot be a proper prefix of
	another formula.  Informally explain why this fact tells us
	that there is only one way to parse a formula.  The latter
	property is called ``unique readability.''


	\item Give an example of a strings $s$ and $u$ such that $s$
	is a proper prefix of $u$ and $K^{*}(s)=K^{*}(u)=1$ Why does
	your example not contradict the conclusions above?
    \end{enumerate}
\end{enumerate}

\end{document}
