\documentclass[12pt]{article}

\newcommand{\es}{\emptyset}
\newcommand{\st}{\mathrel{:}}
\newcommand{\e}{\varepsilon}
\newcommand{\4}{\\\\}
\usepackage{tikz}
\usepackage{amsmath}
\usetikzlibrary{automata,positioning,arrows}

\begin{document}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\centerline{\bf Homework 3 Morally Due Feb 25 at 11:00 AM}
\centerline{\bf THIS HOMEWORK IS TWO PAGES LONG!!!!!!}

\begin{enumerate}
\item
(0 points, but if you actually miss the midterm without telling Dr. Gasarch ahead of time, you will lose 100 points on this homework)
When will the midterm be (give date and time)?
When will the final be (give date and time)?
By when do you have to tell Dr.\ Gasarch that
you cannot make the midterm? 
% For reference:
% Midterm is on Tuesday, March 31, in class
% Final is on Thursday, May 14, 8AM - 10AM
% Must tell Bill by Feb 11 in both cases
\item
(25 points)
The alphabet is $\{a, b\}$.
A {\it JOSH-NFA} is an NFA such that the underlying directed graph has no cycles at all. A language is JOSH-regular if it is accepted by a JOSH-NFA. (NFA acceptance is as usual: a string is accepted by a JOSH-NFA if there is a path that leads to acceptance.)
\begin{enumerate}
\item
(10 points)
Give an example of a language that is regular but not JOSH-regular. Prove your result.
\item
(15 points) 
Fill in the following sentence and prove it (both directions): 

$$L \hbox{ is JOSH-regular if and only if } L \hbox{ is } XXX.$$

\end{enumerate}

\item
(25 points)
Let 
\begin{itemize}
\item $L_1$ be accepted by DFA $M_1 = (Q_1, \Sigma, \delta_1, s_1, F_1)$, and
\item $L_2$ be accepted by DFA $M_2 = (Q_2, \Sigma, \delta_2, s_2, F_2)$. 
\end{itemize}
Formalize the  construction of an NFA for $L_1 \cup L_2$ that Dr. Gasarch did in class. (The construction using $\e$-transitions). That is, define the NFA $(Q, \Sigma, \Delta, s, F)$
that recognizes $L_1 \cup L_2$ in terms of $M_1$ and $M_2$. 
\4
\centerline{\bf GOTO NEXT PAGE FOR MORE HOMEWORK}

\newpage

\item
(25 points)
\begin{enumerate}
\item (25 points) Give an algorithm that does the following. \\
Input: $\alpha$ a regular expression \\
Output: $\beta$ a regular expression for the complement of the language represented by $\alpha$ \\
You may use any procedure described in class (e.g. procedures for intersection, union, complementation, powerset construction, equivalences between NFAs
and DFAs, conversion from NFA to regular expression).
\item (0 points)
Think about: if $\alpha$ is of length $n$, how long is $\beta$? 
\end{enumerate}
\item
(25 points)
Let $L = \{w: \#_a(w) \equiv 0$ (mod 2)$\}$ and the alphabet is $\{a, b\}$.
\begin{enumerate}
    \item (9 points) 
    Draw the DFA that accepts this language.
    \item (8 points)
    Use the $R(i, j, k)$ method to find the regex for this language. YOU MUST USE THIS METHOD EXACTLY AS GIVEN.
    \item (8 points)
    Determine the regex for $L$ WITHOUT using the $R(i, j, k)$ method. It must be a SIMPLE regex. If we cannot understand your regex, YOU WILL GET NO CREDIT.
\end{enumerate}

\end{enumerate}
\end{document}