\documentclass[11pt,twoside]{article}

\usepackage{xspace}
\usepackage{amssymb}

\newcommand{\coursenumber}{CS 6104}
\newcommand{\coursetitle}{Symbolic Computation}
\renewcommand{\docdate}{\textup{June 5, 1996}}
\newcommand{\duedate}{June 12, 1996}
\newcommand{\doctitle}{Grammar and String-Rewriting Homework (Corrected)}

\newcommand{\firstpageheading}[1]{
\vbox to 0pt{\vskip -#1
\hbox to \hsize{\sl \vbox to 8.5pt{}\doctitle\hfill\docdate\hfill \rm 1}\vss}
\nointerlineskip
\vspace*{-15pt}
}

\addtolength{\textwidth}{1.50in}
\addtolength{\textheight}{1.00in}
\addtolength{\evensidemargin}{-1.25in}
\addtolength{\oddsidemargin}{-0.25in}
\addtolength{\topmargin}{-.50in}

% Some new macros

\newcommand{\Grobner}{Gr\"obner\xspace}
\newcommand{\Mathematica}{\emph{Mathematica\/}\xspace}

\newcommand{\cent}{{\rlap{/}c}}

% Macros for Abstract Reduction Systems

\input{reduction}

\begin{document}

\pagestyle{myheadings}
\markboth{\hfill\docdate\hfill\doctitle}{\doctitle\hfill\docdate\hfill}

\firstpageheading{50pt}

\thispagestyle{empty}

\begin{center}
\Large\bf\doctitle\\
\smallskip
\Large\bf\coursenumber: \coursetitle\\
\end{center}

This assignment is worth 5\% of the course grade
and is due by 9:30AM on \duedate.
Submit your solutions as a \LaTeX\ file named \verb,stringanswers.tex,,
plus any supporting files,
by email to \verb,cs6104@ei.cs.vt.edu,.
Explain your solution to each problem.

Help is available by email as well as during my office hours.
It is especially helpful to request clarification or hints by email
to \verb,cs6104@ei.cs.vt.edu,,
so I can send the response to everyone.

\paragraph{Problem 1.}
Let $\Sigma =\{1\}$ be this one-symbol alphabet.
Define a grammar $G_1$ that generates
\begin{eqnarray*}
L_1 & = & \{1^n \mid n \mbox{ is a composite integer}\}.
\end{eqnarray*}
Explain briefly the ideas behind your grammar.

\paragraph{Problem 2.}
Let $\Sigma = \{a_1,a_2,\ldots,a_n\}$ be an alphabet in
which the $n$ symbols have been given an order;
that is,
$a_i>a_j$ if $i>j$.
The {\em lexicographic ordering $\gtlex$\/}
on $\Sigma^*$ is defined so that $x \gtlex y$ if
$y$ is a proper prefix of $x$
or if $x=u a_i v$, $y=u a_j z$, and $i>j$.
The {\em length-lexicographic ordering $\gtlengthlex$\/}
on $\Sigma^*$ is defined so that $x \gtlengthlex y$ if
\begin{enumerate}
\item
$|x| > |y|$ (i.e., longer strings are bigger); or
\item
$|x| = |y|$ and $x \gtlex y$ (i.e., lexicographic order breaks ties).
\end{enumerate}

Let $n=2$, so $\Sigma=\{a_1,a_2\}$.
Define a grammar $G_2$ that computes the
length-lexicographic order of two strings $x,y\in \Sigma^*$.
In particular,
$G_2$ computes the function
\begin{eqnarray*}
f_2(x,y) & = & \left\{
\begin{array}{ll}
\lambda \qquad & \mbox{if } x=y;\\
1 & \mbox{if } x \gtlengthlex y;\\
0 & \mbox{if } y \gtlengthlex x.\\
\end{array}
\right.
\end{eqnarray*}
In particular,
$G_2$ should compute $f_2$
by a derivation
\begin{eqnarray*}
\$x\#yC\cent & \Longrightarrow^*_{G_2} & f_2(x,y)
\end{eqnarray*}
where $x,y\in\Sigma^*$.
There may be a creative way to use nondeterminism in $G_2$,
but this is not necessary.

\paragraph{Problem 3.}
For a grammar $G$,
let $\Sigma_G$ denote the set of terminals of $G$.
Let $L$ be the language:
\begin{eqnarray*}
L_3 & = & \{ \#\alpha(G)\# \mid L(G) = \Sigma^*_G \}.
\end{eqnarray*}
Prove that $L_3$ is not r.e.
and that $\overline{L_3}$ is not r.e.

\paragraph{Problem 4.}
Let $\Sigma=\{a,b\}$.
Give a string-rewriting system $R$ on $\Sigma$
that has equivalence classes $E_n$,
one for each natural number\footnote{For purposes of this course,
the set of natural numbers is $\Bbb{N} = \{0,1,2,\ldots,\}$}
$n$,
such that
\begin{eqnarray*}
E_n & = & \{ x\in\Sigma^* \mid |x|=n\}.
\end{eqnarray*}
Explain briefly the ideas behind your string-rewriting system.

\end{document}
