% Created 2023-09-27 Wed 14:13
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\notindent \notag  \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
\author{Elizabeth Hunt}
\date{\today}
\title{HW 04}
\hypersetup{
 pdfauthor={Elizabeth Hunt},
 pdftitle={HW 04},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 28.2 (Org mode 9.7-pre)}, 
 pdflang={English}}
\begin{document}

\maketitle
\setlength\parindent{20pt}

\section{Question One}
\label{sec:org1166362}
Consider the regular language \(L\) over \(\Sigma = \{0,1,2\}\) such that \(L = \{x^{\star} | x \in \Sigma\}\)
, then \(L\) is a language; its members being all possible combinations of any length of all
\(x \in \Sigma\).

\(L\) is a \uline{regular} language since there is a FA to describe it:

\begin{itemize}
\item \(F = \{q_0\}\)
\item \(\Sigma = \{0,1,2\}\)
\item \(S = q_0\)
\item \(\delta(q_0, 0) = q_0\), \(\delta(q_0, 1) = q_0\), \(\delta(q_0, 2) = q_0\)
\item \(Q = {q_0}\)
\end{itemize}

Let a set of languages \(G\) exist such that \(G_1 = \{0^i 1^i | i \geq 0\}\), \(G_2 = \{(0^i 1^i)(0^i 1^i) | i \geq 0\}\)
\(\cdots\) \(G_n = \{(0^i 1^i)^n | i \geq 0\}\). \(G_1\) is irregular by the proof found in Lecture 5. Then we assume that
\(G_k\) is irregular. If so, we can show \(G_{k+1}\) is irregular because we can only construct a FA to recognize
\(G_{k+1}\) if and only if we can concatenate a FA recognizing \(G_k\) in an epsilon transition with another FA recognizing \(G_1\); which is
not existant. By induction, any such \(G_i | i \in \mathds{N}\) is irregular.

Each \(G\) is also a proper sublanguage since for each \(i \in \mathds{N}\) we can construct \((01)^{i+1}\)
which is not in \(G_i\) but in \(L\), so \(\nexist x \in G | x = L\). For extra clarity we know every string in \(G_i\) is
also in \(L\) since \(L\) is really the Kleene Closure.

Thus there are at least \(\aleph_0\) infinitely many such non-regular proper sublanguages of the regular language \(L\).

\section{Question Two}
\label{sec:orgf857515}
\subsection{One (adapted from slide notes in Lecture 5)}
\label{sec:org606e4e3}
Consider a minimal DFA \(M\) that recognizes \(L\); \(L = L(M)\) with \(k\) states.

Then consider the string \(a^k b^k c^k\); to first recognize \(a^k\) we go through \(k+1\) states, so we can
find a loop in the path taken via \(\delta\) such that there exists \(q = \delta^{\star}(q, a^i) | i > 0\).

If we pump this loop zero times, then for the string \(a^j b^k c^k\), \(j < k\); for one or more times,
\(j > k\); thus \(j < k\) or \(j > k\) but \(j \neq k\), a contradiction from the original definition.

\subsection{Two}
\label{sec:org6221b61}

Any string in this language is an even number of \(a\)'s, recognized by this FA (thus, is a regular language).

\begin{itemize}
\item \(F = \{q_0\}\)
\item \(\Sigma = \{a\}\)
\item \(S = q_0\)
\item \(\delta(q_0, a) = q_1, \delta(q_1, a) = q_0\)
\item \(Q = \{q_0, q_1\}\)
\end{itemize}

\subsection{Three}
\label{sec:org4423d9f}
Consider a minimal DFA \(M\) that recognizes \(L\); \(L = L(M)\) with \(k\) states. By the pumping lemma
each string \(x \in L\) such that \(|x| \geq k\) is of the form \(uvw\) with \(|uv| \leq k\), \(|v| \geq 1\) and
\(uv^i w \in L \forall i \geq 0\).

For any such \(k\) we create the string \(a^k c a^k \in L\), and because \(|uv| \leq k\) then \(uv\) matches at most
\(a^k\). So, \(u = a^m, v = a^n\) with \(m + n \leq k\), and thus \(w = a^{k - (m+n)} c a^k\). Additionally, since \(|v| \geq 1\),
\(n \ge 1\).

By pumping \(v\) zero times we then have \(a^m a^{k-(m+n)}c a^k = a^{k-n} c a^k \notin L\) as \(n \geq 1\) so \(L\) must be irregular.

\subsection{Four}
\label{sec:org719bada}
Consider a minimal DFA \(M\) that recognizes \(L\); \(L = L(M)\) with \(k\) states. By the pumping lemma
each string \(x \in L\) such that \(|x| \geq k\) is of the form \(uvw\) with \(|uv| \leq k\), \(|v| \geq 1\) and
\(uv^i w \in L \forall i \geq 0\).

For any such \(k\) we create the string \(a^k c^k b^{2k} \in L\) and because \(|uv| \leq k\) then \(uv\) matches at most
\(a^k\). So, \(u = a^m, v = a^n\) with \(m + n \leq k\), and since \(|v| \geq 1\), \(n \ge 1\) thus \(w = a^{k - (m+n)} c^k b^{2k}\).
Additionally, since \(|v| \geq 1\), \(n \ge 1\).

By pumping \(v\) zero times we then obtain \(a^m a^{k-(m+n)} c^k b^2k = a^{k-n} c^k b^{2k}\) but then \(k-n + k \neq 2k\) as
\(n \geq 1\), a contradiction; \(L\) is irregular.

\subsection{Five}
\label{sec:org9f5d6ff}
Consider a minimal DFA \(M\) that recognizes \(L\); \(L = L(M)\) with \(k\) states. By the pumping lemma
each string \(x \in L\) such that \(|x| \geq k\) is of the form \(uvw\) with \(|uv| \leq k\), \(|v| \geq 1\) and
\(uv^i w \in L \forall i \geq 0\).

For any such \(k\) we create the string \(0^k 1^{k-1} \in L\), and because \(|uv| \leq k\) then \(uv\) matches at most
\(0^k\). So, \(u = 0^m, v = 0^n\) with \(m + n \leq k\), thus \(w = 0^{k - (m+n)} 1^{k-1}\). Additionally, since \(|v| \geq 1\), \(n \ge 1\).

By pumping \(v\) zero times we obtain the string \(0^m 0^{k-(m+n)} 1^{k-1} = 0^{k-n} 1^{k-1}\) and \(k-n\) cannot be greater than
\(k-1\), a contradiction; \(L\) is irregular.

\section{Question Three}
\label{sec:org9247330}

(pictorial draft) DFA

\begin{center}
\includegraphics[width=200px]{./img/problem_3_dfa.png}
\end{center}

And:

\begin{itemize}
\item \(\Sigma = \{a, b\}\)
\item \(Q = \{q_0, q_1, q_2, q_3\}\)
\item \(F = \{q_2\}\)
\item \(S = q_0\)
\item \(\delta(q_0, a) = q_1\), \(\delta(q_0, b) = \emptyset\), \(\delta(q_1, a) = \emptyset\), \(\delta(q_1, b) = q_2\), \(\delta(q_2, a) = q_3\), \(\delta(q_2, a = q_1)\),
\(\delta(q_3, a) = q_2\), \(\delta(q_3, b) = \emptyset\)
\end{itemize}

We can build a FA that recognizes strings in \(L(G)\), so it is regular.

\section{Question Four}
\label{sec:org7d011c1}
\(G = (\{S\}, \{0,1,\cdots,9\}, S, \{S \rightarrow 0S | 1S | 2S | 3S | 4S | 5S | 6S | 7S | 8S | 9S | \epsilon\})\)
\end{document}