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

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\question}[1]{\vspace{10pt}\noindent $\mathbf{#1}$}

\newtheorem{objective}{Objective}

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

  
  \input{hw_survey}
  
  \section{Regular Expresssions} % (fold)
    
    \question{1.1}
    Give a regular expression to describe the following languages over the alphabet $\Sigma = \{a,b,c\}$.
    \begin{itemize}
      \item $\{w \mid \text{$w$ begins with $a$ and ends with $b$}\}$
      \item $\{w \mid \text{every odd position of $w$ is $c$}\}$
      \item $\{w \mid \text{$w$ has length at most $4$}\}$
      \item $\{w \mid \text{$w$ is any string other than $abc$}\}$
    \end{itemize}

  % section Regular Expressions (end)

  \section{Converting Regular Expressions to NFAs and back} % (fold)
  
    \question{2.1}
      \textbf{$(1)$} Take the following DFA $M$ and add a unique start state and a unique accept state to make an equivalent GNFA.
      
      \[
        \begin{tikzpicture}[scale=0.2]
        \tikzstyle{every node}+=[inner sep=0pt]
        \draw [black] (19.4,-24.7) circle (3);
        \draw (19.4,-24.7) node {$q_1$};
        \draw [black] (19.4,-24.7) circle (2.4);
        \draw [black] (36.8,-24.7) circle (3);
        \draw (36.8,-24.7) node {$q_2$};
        \draw [black] (36.8,-24.7) circle (2.4);
        \draw [black] (27.7,-37.1) circle (3);
        \draw (27.7,-37.1) node {$q_3$};
        \draw [black] (14,-21.1) -- (16.9,-23.04);
        \fill [black] (16.9,-23.04) -- (16.52,-22.18) -- (15.96,-23.01);
        \draw [black] (21.189,-22.306) arc (134.50803:45.49197:9.859);
        \fill [black] (35.01,-22.31) -- (34.79,-21.39) -- (34.09,-22.1);
        \draw (28.1,-18.98) node [above] {$0$};
        \draw [black] (24.837,-36.243) arc (-115.24366:-177.16321:10.022);
        \fill [black] (24.84,-36.24) -- (24.33,-35.45) -- (23.9,-36.35);
        \draw (20.17,-34.09) node [left] {$1$};
        \draw [black] (37.306,-27.644) arc (0.5801:-73.12782:9.364);
        \fill [black] (30.66,-36.7) -- (31.57,-36.95) -- (31.28,-35.99);
        \draw (36.07,-34.67) node [right] {$1$};
        \draw [black] (28.319,-40.024) arc (39.68508:-248.31492:2.25);
        \draw (25.3,-44.21) node [below] {$0$};
        \fill [black] (25.76,-39.37) -- (24.82,-39.5) -- (25.46,-40.27);
        \draw [black] (37.872,-21.911) arc (186.70939:-101.29061:2.25);
        \draw (42.29,-18.66) node [right] {$0$};
        \fill [black] (39.67,-23.85) -- (40.52,-24.26) -- (40.4,-23.26);
        \draw [black] (22.282,-25.489) arc (65.90207:1.69107:9.787);
        \fill [black] (22.28,-25.49) -- (22.81,-26.27) -- (23.22,-25.36);
        \draw (27.03,-27.64) node [right] {$1$};
        \end{tikzpicture}
      \]
      
      \textbf{$(2)$} Remove state $q_3$ using the method described in class to make a GNFA with one fewer state.
      Draw the new state diagram.
      
      \textbf{$(3)$} Remove state $q_2$ using the method described in class to make a GNFA with one fewer state.
      Draw the new state diagram.
      
      \textbf{$(4)$} Give a regular expression $r$ such that $L(r) = L(N)$.
      Ideally, give the regular expression that one gets from running the algorithm given in class and in the book when removing states $q_3$, $q_2$, and $q_1$ in that order.
  
  % section converting_regular_expressions_to_nfas_and_back (end)

  \section{The Pumping Lemma} % (fold)
  
    \question{3.1}
    In the book, it mentions that the language of all binary strings ($\Sigma =\{0,1\}$) with an equal number of $01$ and $10$ substrings is regular.
    Now consider the language $L_1$ of binary strings with twice as many $01$ substrings as $10$ substrings.
    Is $L_1$ regular?  
    If so, give a DFA that recognizes it.  
    Otherwise, use the pumping lemma to prove that $L_1$ is not regular.
    \emph{In case you are wondering, this is a trick question.  There's a trick.}
  
    \question{3.2}
    Let $L_2 = \{www | w\in \{0,1\}^*\}$.
    Is $L_2$ regular?  
    If so, give a DFA that recognizes it.  
    Otherwise, use the pumping lemma to prove that $L_2$ is not regular.    

    \question{3.3}
    Let $\Sigma = \{0,1,2,3,4,5,6,7,8,9,\times,=\}$ and let 
    \[
      L_3 = \{a\times b = c \mid a,b,c \text{ are positive integers (written in decimal) and } a\times b = c\}.
    \]
    Prove that $L_3$ is not regular.
    
    \question{To~think~about:} What if $a$ and $b$ are also required to be less than $100$?  Would that make $L_3$ regular?  
    \emph{Just ponder this one.}
  
  % section the_pumping_lemma (end)
  
\end{document}