<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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 Spring 2022\hfill Due Tuesday, 15 February 2022}}
\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.
\end{enumerate}

\end{document}
</pre></body></html>