\documentclass{article}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{fullpage}
\usepackage{eucal}
\usepackage{graphicx}
\usepackage{color}
\usepackage{tikz}
\usepackage{algorithm,algorithmic}

\newcommand{\Z}{\mathbb{Z}}

\newtheorem{objective}{Objective}

\begin{document}
  
  \begin{minipage}{\textwidth}
    CSE3502 - Theory of Computation \hfill \today\\
    \textbf{Due: Before class on February 4, 2014}\\
    \\
    \centering{Homework 2} \hfill
  \end{minipage}

  
  \input{hw_survey}
  
  \section{Deterministic Finite Automata (DFAs)} % (fold)
    
    \noindent $\mathbf{1.1}$
    The formal description of a DFA is $\{\{a,b,c\}, \{0,1\}, \delta, a, \{a\}\}$,
    where the transition function $\delta$ is defined as
    \[
      \begin{tabular}{c|c|c}
        ~  & 0 & 1\\ \hline
        a & b & a\\  \hline
        b & c & a\\  \hline
        c & b & c\\  \hline    
      \end{tabular}
    \]
    \begin{itemize}
      \item Draw the state diagram for this DFA.
      \item List $5$ words accepted by this DFA.
      \item List $5$ words that are rejected by this DFA.      
    \end{itemize}

  % section DFAs (end)

  \section{Nondeterministic Finite Automata (NFAs)} % (fold)
  
  \noindent $\mathbf{2.1}$
    The formal description of an NFA is $\{\{a,b,c\},\{0,1\},\delta, a, \{c\}\}$, where the transition function $\delta$ is defined as
    \[
      \begin{tabular}{c|c|c|c}
        ~ & 0 & 1 & $\varepsilon$\\ \hline
        a & $\emptyset$ & $\{b\}$ & $\emptyset$ \\  \hline
        b & $\emptyset$ & $\{c\}$ & $\emptyset$ \\  \hline
        c & $\{b,c\}$ & $\emptyset$ & $\emptyset$ \\  \hline    
      \end{tabular}
    \]
    Draw the state diagram for this NFA.
    
  \noindent $\mathbf{2.2}$
  Give a formal description of the following NFA.
  \[
    \begin{tikzpicture}[scale=0.2]
      \tikzstyle{every node}+=[inner sep=0pt]
      \draw [black] (19.2,-28.5) circle (3);
      \draw (19.2,-28.5) node {$a$};
      \draw [black] (19.2,-28.5) circle (2.4);
      \draw [black] (34.3,-28.4) circle (3);
      \draw (34.3,-28.4) node {$b$};
      \draw [black] (49.2,-28.6) circle (3);
      \draw (49.2,-28.6) node {$c$};
      \draw [black] (63.5,-28.4) circle (3);
      \draw (63.5,-28.4) node {$d$};
      \draw [black] (63.5,-28.4) circle (2.4);
      \draw [black] (12.1,-23.5) -- (16.75,-26.77);
      \fill [black] (16.75,-26.77) -- (16.38,-25.9) -- (15.81,-26.72);
      \draw [black] (21.142,-26.232) arc (129.69094:51.06793:8.829);
      \fill [black] (32.33,-26.16) -- (32.02,-25.27) -- (31.39,-26.04);
      \draw (26.72,-23.69) node [above] {$0$};
      \draw [black] (36.579,-26.467) arc (121.48657:56.97538:9.74);
      \fill [black] (46.97,-26.61) -- (46.58,-25.75) -- (46.03,-26.59);
      \draw (41.8,-24.52) node [above] {$0$};
      \draw [black] (52.2,-28.56) -- (60.5,-28.44);
      \fill [black] (60.5,-28.44) -- (59.69,-27.95) -- (59.71,-28.95);
      \draw (56.36,-29.02) node [below] {$0,1$};
      \draw [black] (32.152,-30.477) arc (-55.01855:-124.22257:9.489);
      \fill [black] (21.37,-30.55) -- (21.76,-31.41) -- (22.32,-30.58);
      \draw (26.78,-32.7) node [below] {$1$};
      \draw [black] (61.43,-30.567) arc (-48.2546:-131.7454:18.819);
      \fill [black] (61.43,-30.57) -- (60.5,-30.73) -- (61.17,-31.47);
      \draw (48.9,-35.84) node [below] {$\epsilon$};
    \end{tikzpicture}
  \]

  \clearpage
  \noindent $\mathbf{2.3}$
  The following NFA is not complete.  Answer the following questions about it.
  Suppose that we know the language it accepts \emph{is nonempty and} contains no strings with the letter $z$ and every string it accepts contains a $y$.
  What is the start state?
  What is the set of accept states?

  \[
      \begin{tikzpicture}[scale=0.2]
      \tikzstyle{every node}+=[inner sep=0pt]
      \draw [black] (41.3,-40.4) circle (3);
      \draw (41.3,-40.4) node {$a$};
      \draw [black] (34.6,-29.7) circle (3);
      \draw (34.6,-29.7) node {$b$};
      \draw [black] (46.6,-29.7) circle (3);
      \draw (46.6,-29.7) node {$c$};
      \draw [black] (38.327,-40.263) arc (-105.25039:-190.64263:6.811);
      \fill [black] (33.42,-32.43) -- (32.79,-33.13) -- (33.77,-33.31);
      \draw (33.72,-38.6) node [left] {$y$};
      \draw [black] (36.551,-27.453) arc (126.4387:53.5613:6.818);
      \fill [black] (44.65,-27.45) -- (44.3,-26.58) -- (43.71,-27.38);
      \draw (40.6,-25.62) node [above] {$z$};
      \draw [black] (45.277,-27.02) arc (234:-54:2.25);
      \draw (46.6,-22.45) node [above] {$x,y,z$};
      \fill [black] (47.92,-27.02) -- (48.8,-26.67) -- (47.99,-26.08);
      \draw [black] (42.623,-43.08) arc (54:-234:2.25);
      \draw (41.3,-47.65) node [below] {$x,y$};
      \fill [black] (39.98,-43.08) -- (39.1,-43.43) -- (39.91,-44.02);
      \draw [black] (47.308,-32.595) arc (2.50546:-55.20639:7.646);
      \fill [black] (47.31,-32.6) -- (46.84,-33.42) -- (47.84,-33.37);
      \draw (47.22,-37.42) node [right] {$\varepsilon$};
      \end{tikzpicture}
  \]
  % section NFAs (end)

  \section{Regular Languages} % (fold)

    The \emph{complement} of a language $B$ is the set of finite strings $w$ over the same alphabet such that $w\notin B$.

    \noindent $\mathbf{3.1}$
    Show that, if $M$ is a DFA that recognizes language $B$, swapping the accept and nonaccept states in $M$ yields a new DFA that recognizes the complement of $B$.
    Conclude that the class of regular languages is closed under complement.

    \noindent $\mathbf{3.2}$
    Show by giving an example that, if $M$ is an NFA that recognizes language $C$, swapping the accept and nonaccept states in $M$ doesn't necessarily yield a new NFA that recognizes the complement of $C$.
    (Try to find a small example.)
    Is the class of languages recognized by NFAs closed under complement? Explain your answer.
  
  % section regular_languages (end)
  
\end{document}