InitHEADmain

1 files changed, 146 insertions, 0 deletions

diff --git a/Homework/cs5000/hw04/hw04.tex b/Homework/cs5000/hw04/hw04.tex
new file mode 100644
index 0000000..9aa70a1
--- /dev/null
+++ b/Homework/cs5000/hw04/hw04.tex
@@ -0,0 +1,146 @@
+% 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}
\ No newline at end of file