<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\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 4\\ 
CS 4810/5810 Spring 2025\hfill Due Wednesday, 26 February 2025}}
\end{center}
\medskip

\pagestyle{empty}

\begin{enumerate}
\item
Consider the automaton
\begin{gather*}
\begin{array}{r@{\hspace{1mm}}l|cc}
\multicolumn 2 c {} &amp; a &amp; b\\ \cline{3-4}
\to &amp; 1 &amp; 8 &amp; 6\\
&amp; 2 &amp; 7 &amp; 4\\
&amp; 3F &amp; 3 &amp; 8\\
&amp; 4F &amp; 5 &amp; 7\\
&amp; 5 &amp; 1 &amp; 3\\
&amp; 6F &amp; 6 &amp; 1\\
&amp; 7F &amp; 2 &amp; 4\\
&amp; 8 &amp; 1 &amp; 3
\end{array}
\end{gather*}
\begin{enumerate}
\item
Say which states are accessible.
\item
List the equivalence classes of the equivalence relation $\approx$ defined by
\begin{align*}
p \approx q\ &amp;\Iff\ \forall x\in\Sigma^*\ (\hat\delta(p,x)\in F
\Iff \hat\delta(q,x)\in F).
\end{align*}
Include inaccessible states.
\item
Give the equivalent automaton obtained by collapsing equivalent states and removing inaccessible states.
\end{enumerate}

\item
In Homework 3, you had to show that the set $A = \set{a^n b^m}{2n=3m}$ is nonregular.
\begin{enumerate}
\item
Give a short proof of this fact using homomorphisms. (\emph{Hint}. Construct a homomorphism that relates $A$ to your favorite nonregular set.)

\item
Give another proof of this fact using the Myhill--Nerode theorem. (\emph{Hint}. Let $\equiv_A$ be the coarsest Myhill--Nerode relation for $A$:
\begin{align*}
x \equiv_A y\ &amp;\Iffdef\ \forall z\ (xz\in A \Iff yz\in A).
\end{align*}
Describe the equivalence classes of $\equiv_A$. How many are there?)
\end{enumerate}

\item
Miscellaneous Exercise 30, p.~323. Just decide which one is nonregular and prove that it is nonregular.

\item
(For 5810 students.) For the previous question, prove that the regular one is regular. (\emph{Hint}. Given a DFA with states $Q$, build another automaton whose states are functions $f:Q\to Q$.)
\end{enumerate}

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