\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{xcolor,stmaryrd,bussproofs,mathpartir}
\usepackage{tikz,pgfmath}
\usepgflibrary{shapes}
\usetikzlibrary{arrows,automata,backgrounds}

\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}}
\newcommand\lp{\texttt{(}}
\newcommand\rp{\texttt{)}}
\newcommand\rev{\mathop{\mathsf{rev}}}
\renewcommand\bar\overline

%environment definitions

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

\begin{document}

\begin{center}
\framebox{\parbox\courseheader{\large Introduction to Theory of Computing\hfill Homework 3\\ 
CS 4810/5810 Spring 2025\hfill Due Friday, 14 February $\heartsuit$ 2025}}
\end{center}
\medskip

\pagestyle{empty}

\begin{enumerate}
\item
Give \emph{deterministic} finite automata accepting the set of strings
matching the following regular expressions.
\begin{enumerate}
\item $(01 + 10)^*$
\item $(0 + 1(01^* 0)^* 1)^*$
\end{enumerate}
Try to simplify the automata as much as possible.

\item
Show that the following sets are not regular:
\begin{enumerate}
\item
$\set{a^n b^m}{2n=3m}$
\item
The set PAREN of balanced strings of parentheses $\lp,\rp$.  For example, the
string $\lp\lp\lp\rp\lp\rp\rp\lp\rp\rp$ is in PAREN but the string $\rp\lp\lp\rp$ is not.
\item
The set $\set{x\in\{0,1\}^*}{\rev x = \bar x}$, where $\bar x$ denotes the Boolean complement of $x$ (e.g., $\bar{10010} = 01101$) and $\rev x$ denotes the reverse of $x$ (e.g., $\rev{10010} = 01001$).  For example, $100110$ is in the set.
\end{enumerate}

\item
Exercise 2, p.~304.

\item (For 5810 students.)
Prove the following theorems of Kleene algebra.  Use the axioms and notation of Supplementary Lecture A.  You may use any of the basic properties of Kleene algebra listed in Lecture 9 or Supplementary Lecture A.  We have posted proofs of (9.14)--(9.18) on p.~50 on the Handouts page as an illustration of the style of reasoning we would like to see.
\begin{enumerate}
\item
$x^* = (xx)^* (1+x)$.
\item
$yx = 0 \Imp (x+y)^* = x^* y^*$.\\
Note that this is an implication.  You should try to prove the conclusion $(x+y)^* = x^* y^*$ from the axioms, citing the premise $yx = 0$ where appropriate.
\end{enumerate}
(\emph{Hint}.  Simplify the task by breaking up the equation into two inequalities, one in each direction.  For (b), you will only need to use the premise in one direction.)

\end{enumerate}

\end{document}
