\documentstyle[12pt,simplemargins]{article}
\setallmargins{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{1}

% DEFINE THE DUE DATE
\def\due{September 19, 1991}

% title command
\newcommand{\mytitle}{{\large\noindent 6.035 Computer Language
Engineering \hfill{} Juliet Bourne \\ 
Homework \#\psnum \hfill{} \due \\}
\vspace{-.43in}
\begin{center} \rule{6.5in}{.25mm} \end{center}}
% newpage setup command 
\newcommand{\mypage}[1]{\newpage{\large\noindent 6.035 Computer Language
Engineering \hfill{} Juliet Bourne \\
Homework \# \psnum \hfill{} \due \\}
\vspace{-.43in}
\begin{center} \rule{6.5in}{.25mm} \end{center}}
%\newcommand{\mynewpage}{\newpage\noindent
%{\large 6.035 \hfill{} Juliet Bourne \\
%Problem Set \psnum \hfill{} {\bf Page \thepg} \\}
%\vspace{-.6in}
%\begin{center}
%\rule{6in}{.25mm}
%\end{center}
%\addtocounter{pg}{1}}
% problem command
\newcommand{\prob}[1]{\noindent{\fbox{\large\bf Problem #1}}\vspace{.25in}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}

\newcommand{\PSbox}[3]{\mbox{\rule{0in}{#3}\special{psfile=#1}\hspace{#2}}}

\begin{document}

\mytitle

\prob{1}

\subprob{a} $(1 \mid 01 \mid 001)^* (\lambda \mid 0 \mid 00)$

The language described by this regular expression accepts any number of
the following strings catenated in any order: ``1'', ``01'', and
``001''.  This catenation can also be followed by one, two, or no zeros,
and still be accepted by the language.

Examples: $10111001$, $01$, $\lambda$, $011001010$, $1$, $0011$

\vspace*{.25in}
\subprob{b} $(00 \mid 11 \mid ((01 \mid 10)(00 \mid 11)^* (01 \mid 10)))^*$

The language described by this regular expressions accepts any number of
the following strings catenated together in any order: ``00'', ``11'',
and strings which consist of either ``01'' or ``10'' at the beginning
catenated with any number and order of ``00''s and/or ``11''s and then
followed by ``01'' or ``10''.

Examples: $0100011100111001$, $0011$, $00$, $1101011010$, $\lambda$

\mypage

\prob{2}

\subprob{a} $(0011 \mid 1 \mid 01)^*$

\vspace*{.15in}
The ``0011'' option assures that any pair of zeros will be followed by a
pair of ones. Single zeros can only appear when there is no possibility
that another zero will appear right after it. (Thus the ``01'' option.)
Any number of ones can appear anywhere, thence the ``1'' option.

\subprob{b} $( (nz (nz \mid 0)^*) \mid 0)\,\, .\,\,(((nz \mid 0)^* nz) \mid 0)$

\vspace*{.1in}
where $nz = (1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9)$.

\vspace*{.15in}
\noindent $nz$ appears as a required part of a string at the beginning
and/or the end (if there is more than one digit before and/or after the
decimal point).  This assures that there will be no trailing or leading
zeros in the strings allowed by this regexp.

\mypage

\prob{3}

\subprob{a}

NFA which accept strings following the regexp $(ab^*c)$:

\vspace*{1in}

NFA which accept strings following the regexp $(abc^*)$:

\vspace*{1in}

Thus, the NFA which accepts $(ab^*c) \mid (abc^*)$:

\PSbox{/mit/jcbourne/Psets/6035/nfa.ps voffset=32}{3.75in}{3in}

\subprob{b} The start state of the DFA consists of all states reachable
from the start state of the NFA through $\lambda$-transitions. The
states of the DFA and also the transitions are determined by
systematically exploring every possible path in the NFA reachable from
the start state of the DFA. The states of the DFA usually represent more
than one state in the NFA.  The final states of the DFA are all those
states which contain a final state of the NFA. Thus:

\beq
s_0 & = & \langle s_1 s_2 \rangle \\
F & = & \{ s_5 , s_6 ,\langle s_3 s_6 \rangle , \langle s_5 s_6\rangle \}
\eeq

\noindent(See table on next page for all states and transitions.)

\mypage

\newcommand{\st}[2]{$\langle s_#1 s_#2 \rangle$}

\begin{center}
$\delta(s_i,v) \rightarrow s_f$

\vspace*{.15in}
\begin{tabular}{||c|c|c||c|c|c||}\hline\hline
$s_i$ & $v$ & $s_f$ & $s_i$ & $v$ & $s_f$ \\ \hline\hline

\st{1}{2} & a & \st{3}{4} & $s_x$   & a & $s_x$ \\ \cline{2-3}\cline{5-6}
\mbox{}   & b & $s_x$     & \mbox{} & b & $s_x$ \\ \cline{2-3}\cline{5-6}
\mbox{}   & c & $s_x$     & \mbox{} & c & $s_x$ \\ \hline

\st{3}{4} & a & $s_x$     & $s_5$   & a & $s_x$ \\ \cline{2-3}\cline{5-6}
\mbox{}   & b & \st{3}{6} & \mbox{} & b & $s_x$ \\ \cline{2-3}\cline{5-6}
\mbox{}   & c & $s_3$     & \mbox{} & c & $s_x$ \\ \hline

\st{3}{6} & a & $s_x$     & $s_3$   & a & $s_x$ \\ \cline{2-3}\cline{5-6}
\mbox{}   & b & $s_2$     & \mbox{} & b & $s_2$ \\ \cline{2-3}\cline{5-6}
\mbox{}   & c & \st{4}{6} & \mbox{} & c & $s_3$ \\ \hline

\st{5}{6} & a & $s_x$     & $s_6$   & a & $s_x$ \\ \cline{2-3}\cline{5-6}
\mbox{}   & b & $s_x$     & \mbox{} & b & $s_x$ \\ \cline{2-3}\cline{5-6}
\mbox{}   & c & $s_6$     & \mbox{} & c & $s_6$ \\ \hline\hline
\end{tabular}
\end{center}

\PSbox{/mit/jcbourne/Psets/6035/dfa.ps}{4.25in}{3in}

\subprob{c}

\begin{tabular}{c|l}
state & input \\ \hline
\st{1}{2} & (abbbc) \\
\st{3}{4} & (bbbc) \\
\st{3}{6} & (bbc) \\
$s_3$     & (bc) \\
$s_3$     & (c) \\
$s_3$     & ()
\end{tabular}

\mypage

\prob{4}

\begin{eqnarray}
S &\,\,\,\rightarrow\,\,\,& aB \\
S &\,\,\,\rightarrow\,\,\,& bA \\
A &\,\,\,\rightarrow\,\,\,& a \\
A &\,\,\,\rightarrow\,\,\,& aS \\
A &\,\,\,\rightarrow\,\,\,& bAA \\
B &\,\,\,\rightarrow\,\,\,& b \\
B &\,\,\,\rightarrow\,\,\,& bS \\
B &\,\,\,\rightarrow\,\,\,& aBB
\end{eqnarray}

\subprob{a} Lefmost derivation, starting with S:

\vspace*{.2in}
\begin{tabular}{c|l}
Using Rule & Result \\ \hline
1 & aB \\
8 & aaBB \\
8 & aaaBBB \\
6 & aaabBB \\
6 & aaabbB \\
8 & aaabbaBB \\
6 & aaabbabB \\
7 & aaabbabbS \\
2 & aaabbabbbA \\
3 & aaabbabbba
\end{tabular}

\subprob{b} Rightmost derivation, starting with ``aaabbabbba'', just
reverse the above derivation:

\vspace*{.2in}
\begin{tabular}{c|l}
Using Rule & Result \\ \hline
3 & aaabbabbbA \\
2 & aaabbabbS \\
7 & aaabbabB \\
6 & aaabbaBB \\
8 & aaabbB \\
6 & aaabBB \\
6 & aaaBBB \\
8 & aaBB \\
8 & aB \\
1 & S
\end{tabular}

\mypage

\subprob{c}

\vspace*{4in}

\subprob{d}

\end{document}


