\documentclass[10pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage[normalem]{ulem}
\usepackage[mathscr]{euscript}
\usepackage{inconsolata}
\usepackage{tikz}

\newcommand{\ds}{\displaystyle}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\FF}{\mathscr{F}}
\newcommand{\GG}{\mathscr{G}}
\newcommand{\LL}{\mathscr{L}}
\newcommand{\SSS}{\mathscr{S}}
\newcommand{\CC}{\mathscr{C}}
\newcommand{\ttt}{\texttt}
\newcommand{\Length}{\ttt{Length}}
\newcommand{\MS}{\ttt{MixedShuffle}}



\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}

\title{\sc Math 4931 / 5931 -- Special Topics: Theory of Computation and Formal Languages\\[10pt]Homework 3}
\author{
	Spring 2023\\[10pt]
	due Friday, March 10, \underline{by the beginning of class}
}
\date{}
\begin{document}
\maketitle

\begin{center} 
	\emph{This homework assignment was written in \LaTeX{}. You can find the source code on the course website.}
\end{center}

\textbf{\underline{You must explain your reasoning for all of your answers. Correct answers with no justification or}\\[5pt]\underline{explanation will not be accepted.}}

\textbf{Students enrolled in Math 4931: Complete any 6 out of the 9 problems.}\\
\textbf{Students enrolled in MSSC 5931: Complete any 7 out of the 9 problems.}\\


\begin{enumerate}

	\item Convert the NFA below into a DFA that accepts the same language. Remove any unreachable states, but do not simplify further. 
	
	\begin{center}
	\begin{tikzpicture}[scale=0.2]
		\tikzstyle{every node}+=[inner sep=0pt]
		\draw [black] (33.4,-13.5) circle (3);
		\draw (33.4,-13.5) node {$1$};
		\draw [black] (33.4,-13.5) circle (2.4);
		\draw [black] (19.1,-28.7) circle (3);
		\draw (19.1,-28.7) node {$3$};
		\draw [black] (19.1,-28.7) circle (2.4);
		\draw [black] (34.2,-40.9) circle (3);
		\draw (34.2,-40.9) node {$4$};
		\draw [black] (49.5,-25.2) circle (3);
		\draw (49.5,-25.2) node {$2$};
		\draw [black] (32.729,-38.287) arc (-153.8523:-202.80291:26.674);
		\fill [black] (32.73,-38.29) -- (32.83,-37.35) -- (31.93,-37.79);
		\draw (29.47,-27.32) node [left] {$a$};
		\draw [black] (33.808,-37.926) arc (-173.21228:-183.44294:120.248);
		\fill [black] (33.18,-16.49) -- (32.64,-17.26) -- (33.63,-17.32);
		\draw (32.47,-27.23) node [left] {$a$};
		\draw [black] (34.434,-16.315) arc (17.948:-14.60321:38.755);
		\fill [black] (34.43,-16.32) -- (34.2,-17.23) -- (35.16,-16.92);
		\draw (36.85,-27.12) node [right] {$\varepsilon$};
		\draw [black] (27.5,-6.3) -- (31.5,-11.18);
		\fill [black] (31.5,-11.18) -- (31.38,-10.24) -- (30.6,-10.88);
		\draw [black] (47.07,-23.44) -- (35.83,-15.26);
		\fill [black] (35.83,-15.26) -- (36.18,-16.14) -- (36.77,-15.33);
		\draw (43.15,-18.85) node [above] {$a,b$};
		\draw [black] (52.18,-23.877) arc (144:-144:2.25);
		\draw (56.75,-25.2) node [right] {$\varepsilon$};
		\fill [black] (52.18,-26.52) -- (52.53,-27.4) -- (53.12,-26.59);
		\draw [black] (36.29,-38.75) -- (47.41,-27.35);
		\fill [black] (47.41,-27.35) -- (46.49,-27.57) -- (47.21,-28.27);
		\draw (42.38,-34.52) node [right] {$a$};
		\draw [black] (35.523,-43.58) arc (54:-234:2.25);
		\draw (34.2,-48.15) node [below] {$b$};
		\fill [black] (32.88,-43.58) -- (32,-43.93) -- (32.81,-44.52);
		\draw [black] (16.42,-30.023) arc (324:36:2.25);
		\draw (11.85,-28.7) node [left] {$b$};
		\fill [black] (16.42,-27.38) -- (16.07,-26.5) -- (15.48,-27.31);
		\draw [black] (19.823,-25.792) arc (161.45006:112.04487:18.715);
		\fill [black] (30.54,-14.4) -- (29.61,-14.24) -- (29.99,-15.16);
		\draw (23.4,-17.46) node [left] {$b$};
	\end{tikzpicture}
	\end{center}
	
	\item Use the construction of Lemma 1.55 to find an NFA that accepts the same language as the regular expression $(\{a\} \cup \{b\})^*(\{aa\} \cup \{bb\})(\{a\} \cup \{b\})^*$. Don't attempt to simplify. Your answer will have many states---draw it on a separate paper first so that you can draw it very neatly on your final submission.

	\item Use the construction of Lemma 1.60 to find a regular expression that accepts the same language as the DFA below. \emph{Show the GNFAs in each intermediate step.}
	
	\begin{center}
	\begin{tikzpicture}[scale=0.1]
		\tikzstyle{every node}+=[inner sep=0pt]
		\draw [black] (32.2,-14.8) circle (3);
		\draw [black] (32.2,-14.8) circle (2.4);
		\draw [black] (19.3,-29.9) circle (3);
		\draw [black] (19.3,-29.9) circle (2.4);
		\draw [black] (43.8,-29.9) circle (3);
		\draw [black] (43.8,-29.9) circle (2.4);
		\draw [black] (30.5,-41.3) circle (3);
		\draw [black] (26.2,-7.5) -- (30.3,-12.48);
		\fill [black] (30.3,-12.48) -- (30.17,-11.55) -- (29.4,-12.18);
		\draw [black] (33.771,-12.258) arc (176.00538:-111.99462:2.25);
		\draw (38.55,-9.93) node [right] {$a$};
		\fill [black] (35.17,-14.5) -- (35.94,-15.06) -- (36.01,-14.06);
		\draw [black] (34.777,-16.331) arc (55.38549:19.67831:21.973);
		\fill [black] (42.99,-27.02) -- (43.19,-26.09) -- (42.25,-26.43);
		\draw (40.29,-19.62) node [right] {$b$};
		\draw [black] (32.552,-43.472) arc (71.10273:-216.89727:2.25);
		\draw (33.93,-48.33) node [below] {$a,b$};
		\fill [black] (30.02,-44.25) -- (29.29,-44.85) -- (30.24,-45.17);
		\draw [black] (32.552,-43.472) arc (71.10273:-216.89727:2.25);
		\fill [black] (30.02,-44.25) -- (29.29,-44.85) -- (30.24,-45.17);
		\draw [black] (40.8,-29.9) -- (22.3,-29.9);
		\fill [black] (22.3,-29.9) -- (23.1,-30.4) -- (23.1,-29.4);
		\draw (31.55,-29.4) node [above] {$b$};
		\draw [black] (41.58,-27.883) arc (-134.1454:-150.7908:45.38);
		\fill [black] (33.58,-17.46) -- (33.53,-18.41) -- (34.4,-17.92);
		\draw (36.63,-24.37) node [left] {$a$};
		\draw [black] (17.459,-27.546) arc (245.76829:-42.23171:2.25);
		\draw (17.33,-22.71) node [above] {$b$};
		\fill [black] (20.05,-27.01) -- (20.83,-26.48) -- (19.92,-26.07);
		\draw [black] (21.4,-32.04) -- (28.4,-39.16);
		\fill [black] (28.4,-39.16) -- (28.19,-38.24) -- (27.48,-38.94);
		\draw (24.37,-37.07) node [left] {$a$};
	\end{tikzpicture}
	\end{center}

	\item For any language $\LL$, define the language $\Length(\LL)$ over the single-letter alphabet $\Sigma = \{\#\}$ by:
	\[
		\Length(\LL) = \{w \in \Sigma^* : |w| = |v| \text{ for some $v \in \LL$}\}.
	\]
	Prove that if $\LL$ is regular then so is $\Length(\LL)$.
	
	\item Let $\LL$ be a language of words over an alphabet $\Sigma$ and assume $1 \in \Sigma$. Define $\ttt{insert1}(\LL)$ to be the language of words you get by inserting a single $1$ into every word of $\LL$ in every possible way. Formally,
	\[
		\ttt{insert1}(\LL) = \{x \circ 1 \circ y : x \circ y \in \LL\}.
	\]
	Prove that if $\LL$ is regular, then so is $\ttt{insert1}(\LL)$. (Note: we did a simpler version of this in class in which we assumed $1 \not\in \Sigma$.)
	
	\item For two languages $\FF$ and $\GG$, define $\MS(\FF)$ to be the language of words that you get by mixing up words from $\FF$ and $\GG$ back and forth. (This is like the ``perfect shuffle'' language from Homework 2, except that one interleaved two words by alternating letters back and forth, this one interleaves two words using chunks of letters at a time.) Formally,
	\[
		\MS(\FF, \GG) = \{w : w = f_1 \circ g_1 \circ f_2 \circ g_2 \circ \cdots \circ f_k \circ g_k\text{ where }f_1 \circ \cdots \circ f_k \in \FF\text{ and }g_1 \circ \cdots \circ g_k \in \GG\}.
	\]
	For example if $abb \in \FF$ and $acdc \in \GG$, then one example of a word in $\MS(\FF, \GG)$ is $ababcdc$ because
	\[
		ababcdc = ab \circ a \circ b \circ cdc,
	\]
	which has the form $f_1 \circ g_1 \circ f_2 \circ g_2$ where $f_1 \circ f_2 = abb \in \FF$ and $g_1 \circ g_2 = acdc \in \GG$.
	
	Prove that $\FF$ and $\GG$ are regular, then so is $\MS(\FF, \GG)$.

	\item Prove that if $\LL$ is regular then so is $\{w : w \circ w^R \in \LL\}$. (Recall that $w^R$ means the reverse of $w$.)

	\item Consider the language
	\[
		\SSS = \{x \circ y : x \in \{a,b\}^*\text{ and }y \in \{a,b\}^* \text{ and the number of $a$'s in $x$ is equal to the number of $b$'s in $y$}\}.
	\]
	Prove that $\SSS$ is regular.
	
	\item Assume $\Sigma = \{0,1\}$. Let
	\[
		\LL_1 = \{w : \text{$w$ begins with a $1$ and ends with a $0$}\}
	\]
	and let
	\[
		\LL_2 =\{w : \text{$w$ contains at least three $1$s}\}.
	\]
	\begin{enumerate}
		\item Find an NFA for $\LL_1 \cup \LL_2$.
		\item Find an NFA for $\LL_1 \circ \LL_2$.
		\item Find an NFA for $(\LL_2)^*$.
	\end{enumerate}
	
	
\end{enumerate}
\end{document}


