<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[10pt]{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}
\renewcommand\emptyset{\varnothing}
\newcommand\Imp{\Rightarrow}
\renewcommand\hat{\widehat}
\newcommand\set[2]{\{#1\mid#2\}}
\newcommand\Iff\Leftrightarrow
\newcommand\Iffdef{\stackrel{\mathrm{def}}\Leftrightarrow}

%environment definitions

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

\begin{document}

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

\pagestyle{empty}

\begin{enumerate}
\item
Homework 8 Exercise 2(d), p.~309.

\item
Homework 9 Exercise 2, p.~310. (\emph{Note}. This is very easy. If you find yourself doing a complicated construction, you are on the wrong track.)

\item
Homework 9 Exercise 4, p.~310. Enumeration machines are defined in Lecture 30, pp.~225--227. Use the following order on strings: $x &lt; y$ if $x$ is shorter than $y$, and among strings of the same length, $x &lt; y$ if $x$ is lexicographically less than $y$ with respect to some fixed total ordering of the alphabet. For example, with respect to the total order $a &lt; b$ on $\{a,b\}$,
\begin{gather*}
\eps &lt; a &lt; b &lt; aa &lt; ab &lt; ba &lt; bb &lt; aaa &lt; aab &lt; \cdots
\end{gather*}

\item
Miscellaneous Exercise 110, p.~343.
\end{enumerate}

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