InitHEADmain

1 files changed, 106 insertions, 0 deletions

diff --git a/Homework/cs5000/hw04/hw04.org b/Homework/cs5000/hw04/hw04.org
new file mode 100644
index 0000000..fced560
--- /dev/null
+++ b/Homework/cs5000/hw04/hw04.org
@@ -0,0 +1,106 @@
+#+TITLE: HW 04
+#+AUTHOR: Elizabeth Hunt
+#+STARTUP: entitiespretty fold inlineimages
+#+LATEX_HEADER: \notindent \notag  \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
+#+LATEX: \setlength\parindent{20pt}
+#+OPTIONS: toc:nil
+
+* Question One
+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 _regular_ language since there is a FA to describe it:
+
++ $F = \{q_0\}$
++ $\Sigma = \{0,1,2\}$
++ $S = q_0$
++ $\delta(q_0, 0) = q_0$, $\delta(q_0, 1) = q_0$, $\delta(q_0, 2) = q_0$
++ $Q = {q_0}$
+
+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$.
+
+* Question Two
+** One (adapted from slide notes in Lecture 5)
+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.
+
+** Two
+
+Any string in this language is an even number of $a$'s, recognized by this FA (thus, is a regular language).
+
++ $F = \{q_0\}$
++ $\Sigma = \{a\}$
++ $S = q_0$
++ $\delta(q_0, a) = q_1, \delta(q_1, a) = q_0$
++ $Q = \{q_0, q_1\}$
+
+** Three
+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.
+
+** Four
+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.
+
+** Five
+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.
+
+* Question Three
+
+(pictorial draft) DFA
+
+#+attr_latex: :width 200px
+[[./img/problem_3_dfa.png]]
+
+And:
+
++ $\Sigma = \{a, b\}$
++ $Q = \{q_0, q_1, q_2, q_3\}$
++ $F = \{q_2\}$
++ $S = q_0$
++ $\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$
+
+We can build a FA that recognizes strings in $L(G)$, so it is regular.
+
+* Question Four
+$G = (\{S\}, \{0,1,\cdots,9\}, S, \{S \rightarrow 0S | 1S | 2S | 3S | 4S | 5S | 6S | 7S | 8S | 9S | \epsilon\})$