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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
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}
|
