1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
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\})$
|
