\documentclass[11pt]{article}
\usepackage[letterpaper,margin=1in]{geometry}
\usepackage{amsmath,amsthm,amssymb,latexsym}
\usepackage{array,multirow,alltt,enumerate,bbm,eucal,graphicx}
\usepackage[colorlinks]{hyperref}
\usepackage{mathpazo,xcolor,stmaryrd,bussproofs,mathpartir}
\usepackage{tikz,pgfmath}
\usepgflibrary{shapes}
\usetikzlibrary{arrows,automata,backgrounds,calc}

\setlength\parindent{0in}
\addtolength\parskip{1ex}
\setlength\fboxrule{.5mm}\setlength{\fboxsep}{1.2mm}
\newlength\courseheader
\courseheader=\textwidth
\addtolength\courseheader{-4mm}
\parindent=0pt
\parskip=1ex

%macro definitions

\newcommand\eps{\varepsilon}
\newcommand\Imp{\Rightarrow}
\renewcommand\hat{\widehat}
\newcommand\set[2]{\{#1\mid#2\}}
\newcommand\boldeps{\text{\boldmath$\eps$}}
\newcommand\boldemptyset{\text{\bf\o}}

%environment definitions

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\begin{document}

\begin{center}
\framebox{\parbox\courseheader{\large Introduction to Theory of Computing\hfill Homework 2\\ 
CS 4810/5810 Spring 2025\hfill Due Wednesday, 5 February 2025}}
\end{center}
\medskip

\pagestyle{empty}

\begin{enumerate}
\item
Consider the following nondeterministic finite automaton with states $\{s,t,u,v\}$.
\begin{center}
  \tikzset{state/.append style={inner sep=0pt, minimum size=4mm}}
  \tikzset{initial/.append style={initial distance=4mm, initial text=}}
    \small
    \begin{tikzpicture}[->, >=stealth', node distance=20mm, auto, bend angle=16]
      \small
      \node[state, initial, accepting] (0) {$s$};
      \node[state, below of=0] (1) {$t$};
      \node[state, right of=1] (2) {$u$};
      \node[state, above of=2] (3) {$v$};
      \path (3) edge node {$b$} (2);
      \path (2) edge node {$b$} (1);
      \path (1) edge node {$b$} (0);
      \path (1) edge node[swap, pos=.25, xshift=-1pt, yshift=1pt] {$a$} (3);
      \path (0) edge node[pos=.25, xshift=-1pt, yshift=-1pt] {$a$} (2)
                edge node {$a$} (3);
    \end{tikzpicture}
\end{center}
Construct an equivalent deterministic automaton using the subset construction. Show clearly which subset of $\{s,t,u,v\}$ corresponds to each state of the deterministic automaton. Omit inaccessible states.

\item
Show that if $A$ is regular, then so is the set $\set{x\in\Sigma\star}{xxx\in A}$.  See Exercise 26, p.~322, its hint on p.~351, and its solution on p.~358 for a possible approach.

\item
Exercise 7(b), p.~318. You may use part (a) without proof.

\item
Give regular expressions for each of the following subsets of $\{a,b\}\star$.
\begin{enumerate}
\item $\set x {\text{$x$ contains an even number of $a$'s}}$
\item $\set x {\text{$x$ contains an odd number of $b$'s}}$
\item $\set x {\text{$x$ contains an even number of $a$'s or an odd number of $b$'s}}$
\item $\set x {\text{$x$ contains an even number of $a$'s and an odd number of $b$'s}}$
\end{enumerate}
Try to simplify the expressions as much as possible.  Recall that
regular expressions over $\{a,b\}$ may use $\boldeps$,
$\boldemptyset$, $a$, $b$, and operators $+$, $\star$, and
concatenation only; the other pattern operators are not allowed.

\item
(For 5810 students.)
Consider the following NFA over the input alphabet $\{a\}$. All transitions shown are $a$-transitions. The accept state is black, non-accept states are white.
\begin{center}
 \tikzstyle{state}=[circle, inner sep=2pt, draw=black]
 \tikzstyle{accepting}=[fill=black]
 \tikzset{initial/.append style={initial distance=4mm, initial text=, initial where=above}}
  \small
  \begin{tikzpicture}[->, >=stealth', node distance=20mm, auto, bend angle=25]
   \small
   \node (center) {};
   \node[state, initial, accepting] (0) at (90:15mm) {};
   \foreach \x in {1,...,4}
    { \node[state] (\x) at ($(90-\x*72:15mm)$) {}; };
   \foreach \x/\y in {0/1,1/2,2/3,3/4,4/0}
    { \path (\x) edge node {} (\y); };
   \foreach \x/\y in {0/2,1/3,2/4,3/0,4/1}
    { \path (\x) edge node {} (\y); };
  \end{tikzpicture}
\end{center}
What is the set accepted by this automaton? Justify your answer.
\end{enumerate}

\end{document}
