\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{3}

% DEFINE THE DUE DATE
\def\due{March 1, 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{.2in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}

\begin{document}

\mytitle

\prob{1: Regular or Not?}

\subprob{a} Is $L = \bigcup_{i=0}^{\infty} L_i$ regular?

No. A finite automaton cannot be constructed, since, with an infinite
number of languages, an infinite number of states would be required in
the FA to accept $L$. As a concrete counterexample, consider the regular
languages $L_i = \{ a^ib^i \}$. Taking the infinite union of these
regular languages produces a language which has been proven to be
non-regular: $L = \bigcup_{i=0}^{\infty} L_i = \{ a^nb^n | n \geq 0 \}$.

\subprob{b} If $L$ is regular, is $Suffix(L) = \{w : \exists y \in
\Sigma^*$ such that $yw \in L\}$ regular?

Yes. A finite automaton can be constructed that will accept {\em
Suffix(L)}. Let $M$ be the machine which accepts $L$ and $M_s$ the
machine which accepts $Suffix(L)$. $M_s$ would simply consist of a start
state with empty transitions to each state of $M$. Its set of final
states would be exactly the set of final states of $M$.

\subprob{c} If $L_1 \cap L_2$ is regular and $L_1$ is finite, is $L_2$
regular?

No. Since $L_1$ is finite, $L_1 \cap L_2$ must be finite and therefore
regular. Thus, $L_2$ need not be finite or regular. Concrete
counterexample: Let $L_1 = \{ a^2b^2 \}$, which is regular, and $L_2 =
\{ a^nb^n | n \geq 0 \}$, which is not regular. Their intersection, $L_1
\cap L_2 = \{ a^2b^2 \}$, is regular. 

\subprob{d} If $L_1 \cap L_2$ is regular and $L_1$ is regular, is $L_2$
regular?

No. Let $L_1 = L(1*0)$, which is regular, and $L_2= \{ 1^n0^n | n \geq 0
\}$, which is not regular. Their intersection, $L_1 \cap L_2 = \{10\}$, is
regular. 

\mypage

\prob{2: Regular Expressions $\Longleftrightarrow$ NFA}

\subprob{a} $(ba \cup b)^* \cup (bb \cup a)^*$

\vspace*{1in}

\subprob{b}

\vspace*{1in}
Create new start and final states:

\vspace*{1in}
Replace parallel arrows with regexps:

\vspace*{1in}
Replace nodes with regexps:

\vspace*{2.5in}
So, the regexp for this NFA is: $(b(a \cup b) \cup a(a \cup b))^*$

\mypage

\prob{3: Non-regular Languages}

\noindent Prove that the following languages are not regular.

\subprob{a} $L = \{ w \in \{0,1\}^* : w$ has more 0's than 1's$\}$

Assume $L$ is regular. Then $L \cap 1^*0^*$ should be regular since both
$L$ and $1^*0^*$ are regular. However, $L \cap 1^*0^* = \{ 1^n0^{m+n} |
\, m,n \geq 1\}$ can be shown to be non-regular by the pumping theorem
as follows:

Assume $L' = \{ 1^n0^{m+n} | \, m,n \geq 1\}$ is regular. Therefore,
$\exists w = xyz \in L'$ such that $\forall p : \, xy^pz \in L'$. 

Case 1: $y$ consists only of 0's. For $p = 0$, $xy^pz \not\in L'$.
If the string consists of only one more 1 than 0's and if $y$ consists
of one 1, then removing $y$ results in a string which has an equal
number of 1's and 0's and therefore is not in $L'$.

Case 2: $y$ consists of 0's and 1's. For $p > 1$, $xy^pz \not\in L'$.
A 0 would precede a 1 in the string, and therefore the string
would not be in $L'$.

Case 3: $y$ consists only of 1's. For $p = 2$,  $xy^pz \not\in L'$. 
If the string consists of only one more 1 than 0's, then $xy^2z$ would
have more 1's than 0's and therefore would not be in $L'$.

So, $L'$ is not regular since it fails to satisfy the pumping theorem.
Thus, the intersection of $L$ and a regular language is not regular, so
$L$ is not regular.

\subprob{b} $L = \{0^m1^n0^{m+n} : m,n \geq 1\}$

Assume L is regular. Then $\exists w = xyz \in L$ such that $\forall p
: \, xy^pz \in L$.  

Case 1: $y$ consists of only 0's before the 1's.  For $p = 2$, $xy^pz
\not\in L'$. The resulting string would be $0^{m+1}1^n0^{m+n}$ which is
not in the language.

Case 2: $y$ consists of only 1's.  For $p = 2$,  $xy^pz \not\in L'$.
The resulting string would be $0^m1^{n+1}0^{m+n}$ which is not in the
language. 

Case 3: $y$ consists of only 0's after the 1's.  For $p = 2$,  $xy^pz
\not\in L'$. The resulting string would be  $0^m1^n0^{m+n+1}$ which is
not in the language.

Therefore, since the pumping theorem doesn't hold for $L$, $L$ is not
regular.

\subprob{c} $L = \{ w\bar{w} : \, w \in \{0,1\}^*\}$

Assume L is regular. Then $\exists w = xyz \in L$ such that $\forall p :
\, xy^pz \in L$.  However, whatever $y$ is chosen, when it is pumped up,
the $w\bar{w}$ property of the string will be destroyed since the
changes in $w$ will not be reflected in $\bar{w}$ and vice-versa.
Therefore, $xy^pz \not\in L$. So, $L$ is not regular.

\mypage

\prob{4: Deciding Properties of regular languages}

\noindent Argue that there are algorithms to answer the following
questions.

\subprob{a} Given DFAs $M_1$ and $M_2$, does $L(M_1) = \overline{L(M_2)}$?

A DFA $M'_2$ can be constructed such that $L(M'_2) = \overline{L(M_2)}$. By
theorem 2.4.2, there is an algorithm such that, given $M_1$ and $M'_2$,
it can be determined if $L(M_1) = L(M'_2)$, and therefore is $L(M_1) =
\overline{L(M_2)}$,

\subprob{b} Given DFAs $M_1$ and $M_2$, is the set of strings accepted
by both $M_1$ and $M_2$ precisely $(01)^*$?

A DFA $M_{re}$ can be constructed which accepts precisely $(01)^*$, by
the conversion procedure of regular expressions to finite automata. A
DFA $M_{1\cap 2}$ can be constructed which accepts only those strings
that both $M_1$ and $M_2$ accept. The start state $s$ of $M_{1\cap 2}$
would have empty transitions to the start state of both $M_1$ and $M_2$.
The set of final states of $M_{1\cap 2}$ would be $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\}$. If $L(M_{re}) = L(M_{1\cap 2})$, then the set of strings that
are accepted by $M_1$ and $M_2$ is precisely $(01)^*$. And by Theorem
2.4.2, there is an algorithm to find if $L(M_{re}) = L(M_{1\cap 2})$.

\subprob{c} Given a regular expressions $\alpha$, does $L(\alpha)$
contain a string which has at least as many 0's as 1's?

\mypage

\prob{5: 2-state Finite Automata}

\end{document}
