\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

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

% DEFINE THE DUE DATE
\def\due{February 22, 1991}

% title command
\newcommand{\mytitle}{{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
% newpage setup command 
\newcommand{\mypage}[1]{\newpage{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
%\newcommand{\mynewpage}{\newpage\noindent
%{\large 6.045/18.400 \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*}}

\begin{document}

\mytitle

\prob{1: Regular Expressions $\Rightarrow$ NFA}

\noindent Construct an NFA for the regular expression $10\cup (0\cup
11)0^*1$. 

\mypage

\prob{2: Closure of Regular Languages}

\noindent Assume that $L_1$ and $L_2$ are regular languages.

\subprob{a} Prove that $L_1 \cap L_2$ is regular by describing a finite
automaton that accepts it.

\vspace*{.25in}
Let $L_1 = L(M_1)$ and $L_2 = L(M_2)$. Let $M$ be the finite automaton
for which $L(M) = L_1 \cap L_2$. $M$ therefore accepts all strings which
are accepted by {\bf both} $M_1$ and $M_2$. If $M_1 = (K_1, \Sigma{},
\Delta{}_1, s_1, F_1)$ and $M_2 = (K_2, \Sigma{}, \Delta{}_2, s_2,
F_2)$, then $M = (K, \Sigma{}, \Delta{}, s, F)$ such that:

\beq
K & = & K_1 \cup K_2 \cup \{ s \} \\
\Delta & = & \Delta{}_1 \cup \Delta{}_2 \cup \{ s, \varepsilon{}, s_1 \}
\cup \{ s, \varepsilon{}, s_2 \} \\
F & = & \{ (q_1,q_2) | \,\, (s_1,w) \vdash^* (q_1, \varepsilon{})
\,\,\,\&\,\,\, (s_2,w) \vdash^* (q_2, \varepsilon{}) \,\,\,\&\,\,\, 
q_1 \in F_1 \,\,\,\&\,\,\, q_2 \in F_2 \,\,\,\&\,\,\, w \in \Sigma \}
\eeq

\subprob{b} Prove that $L_1 - L_2$ is regular.

\vspace*{.25in}
Let $L(M) = L_1 - L_2$, where $L_1 = L(M_1)$ and $L_2 = L(M_2)$. Thus
the FA $M$ accepts all strings that are accepted by $M_1$ but {\bf not}
by $M_2$. So, If $M_1 = (K_1, \Sigma{}, \Delta{}_1, s_1, F_1)$ and $M_2
= (K_2, \Sigma{}, \Delta{}_2, s_2, F_2)$, then $M = (K, \Sigma{},
\Delta{}, s, F)$ such that:

\beq
K & = & K_1 \cup K_2 \cup \{ s \} \\
\Delta & = & \Delta{}_1 \cup \Delta{}_2 \cup \{ s, \varepsilon{}, s_1 \}
\cup \{ s, \varepsilon{}, s_2 \} \\
F & = & \{ (q_1, q_2) | \,\, (s_1,w) \vdash^* (q_1, \varepsilon{})
\,\,\,\&\,\,\, (s_2,w) \vdash^* (q_2, \varepsilon{}) \,\,\,\&\,\,\,
q_1 \in F_1 \,\,\,\&\,\,\, q_2 \in F_2 \,\,\,\&\,\,\, w \in \Sigma \}
\eeq

\mypage

\prob{3: DFA $\Rightarrow$ NFA}

\noindent For each of the following NFA's, construct an equivalent DFA.

\subprob{a}

\vspace*{4.5in}

\subprob{b}

\mypage

\prob{4: Regular Languages}

\noindent Let $L$ be a regular language. Show that {\em A = \{ x}: for any
$w \in L, x$ does not contain $w$ as a substring \} is regular.

\vspace*{.25in}
If $\bar{A}$ is shown to be regular, i.e. a finite automaton can be
constructed to accept the language $\bar{A}$, then the language $A$ is
regular. So, let $\bar{A} =$ {\em \{ x'}: for any $w \in L$, $x'$
contains $w$ as a substring\}. If $L(M) = L$ and $M = (K, \Sigma{},
\Delta{}, s, F)$, then let $\bar{A} = L(M')$ where $M' = (K', \Sigma{},
\Delta{}', s', F')$ such that:

\beq
K' & = & K \cup \{ s' \} \cup F' \\
\Delta{}' & = & \Delta \cup \{ (s',\sigma{},s') | \,\, \sigma \in \Sigma \} 
\cup (s',\varepsilon{},s) \cup \{ (q,\varepsilon{},f) | \,\, q \in F
\,\,\,\&\,\,\, f \in F' \} \\
& & \cup \{ (f,\sigma{},f) | \,\, f \in F' \,\,\,\&\,\,\, \sigma \in \Sigma \}
\eeq

\mypage

\prob{5: DFA Construction}

\noindent Let {\em L = \{w : w} is a binary representation of an integer
$n$, where $n$ is a multiple of 3 \}.

\subprob{a} Show that $L$ is regular by constructing a DFA which accepts
$L$.

\vspace*{2.5in}

\subprob{b} Give a regular expression describing $L$.

\end{document}
