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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
|
% Created 2023-10-06 Fri 20:58
% 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 (A02364151)}
\date{\today}
\title{Theory of Computability Midterm 1}
\hypersetup{
pdfauthor={Elizabeth Hunt (A02364151)},
pdftitle={Theory of Computability Midterm 1},
pdfkeywords={},
pdfsubject={},
pdfcreator={Emacs 28.2 (Org mode 9.7-pre)},
pdflang={English}}
\begin{document}
\maketitle
\setlength\parindent{20pt}
\section{Problem 1}
\label{sec:orgb0784e8}
\subsection{Stage 1}
\label{sec:org855b93a}
We skip Stage 1; there are no productions in the form \(A \rightarrow BC\) or \(A \rightarrow s\).
\(P' = \{ \}\)
\subsection{Stage 2}
\label{sec:org325eccc}
\(P' = \{ C_a \rightarrow a , C_b \rightarrow b, C_c \rightarrow c, C_d \rightarrow d \}\)
And our new productions are \(\{ S \rightarrow C_a S C_b C_b , S \rightarrow C_a S C_a , S \rightarrow C_b S C_a C_a , S \rightarrow C_b S C_b , S \rightarrow C_c C_d \}\)
\subsection{Stage 3}
\label{sec:orgeecaa22}
We replace \(S \rightarrow C_a S C_b C_b\) with \(\{ S \rightarrow C_a D_1 , D_1 \rightarrow S D_2 , D_2 \rightarrow C_b C_b \}\)
We replace \(S \rightarrow C_a S C_a\) with \(\{ S \rightarrow C_a D_3, D_3 \rightarrow S C_a \}\)
We replace \(S \rightarrow C_b S C_a C_a\) with \(\{ S \rightarrow C_b D_4 , D_4 \rightarrow S D_5 , D_5 \rightarrow C_a C_a \}\)
We replace \(S \rightarrow C_b S C_b\) with \(\{ S \rightarrow C_b D_6 , D_6 \rightarrow S C_b \}\).
We add \(S \rightarrow C_c C_d\) as it is in CNF already.
Thus,
\begin{align*}
P' &= \{ C_a \rightarrow a , C_b \rightarrow b, C_c \rightarrow c, C_d \rightarrow d \} \\
& \cup \{ S \rightarrow C_a D_1 , D_1 \rightarrow S D_2 , D_2 \rightarrow C_b C_b \} \\
& \cup \{ S \rightarrow C_a D_3, D_3 \rightarrow S C_a \} \\
& \cup \{ S \rightarrow C_b D_4 , D_4 \rightarrow S D_5 , D_5 \rightarrow C_a C_a \} \\
& \cup \{ S \rightarrow C_b D_6 , D_6 \rightarrow S C_b \} \\
& \cup \{ S \rightarrow C_c C_d \}
\end{align*}
\section{Problem 2}
\label{sec:orgde63c33}
\begin{center}
\includegraphics[width=150px]{./img/prob_2_parse_tree.png}
\end{center}
Yes, we can recognize the string by this derivation.
\section{Problem 3}
\label{sec:org4d6de8f}
Because strings in \(L(M_1)\) and \(L(M_2)\) are recognized by Discrete Finite Automata,
they must be regular languages.
By the Myhill-Nerode theorem, if \(L\) is a regular language it can be recognized by a unique DFA
with a minimal number of states. In other words, we know that if two DFA recognize
the same language, they must have the same minimal DFA.
Let \(\text{minimize}(D)\) be the minimization algorithm given in Lecture 04 returning a deterministic
set of states.
Then, we know \(M_1\) is equivalent to \(M_2\) when \(\text{minimize}(M_1)\) is congruent to
\(\text{minimize}(M_2)\). This is only true when all descriptors (\(\Sigma\), q\textsubscript{0}, \(\delta\), etc\ldots{}) are also
equivalent.
In the below pseduo code we just check the equivalence of the set of states, alphabet, and start
state. Then we perform a search to see if \((\delta_1) = M_1\) is \(\subseteq\) of \((\delta_2) = M_2\) and
\(\delta_2 \subseteq \delta_1\), and if both are true, then \(\delta_1 = \delta_2\).
If all are equivalent, then the languages recognize the same strings!
\begin{verbatim}
def minimize(dfa):
minimized = dfa.copy()
# ... mutate minimized according to minimize()
return minimized
def delta_subseteq(start_state, sigma, delta1, delta2):
visited = set()
for transition in delta2.keys():
if transition not in delta1 or \
delta1[transition] != delta2[transition]:
return False
return True
def equivalent(m1, m2):
minimized_m1 = minimize(m1)
minimized_m2 = minimize(m2)
if minimized_m1.Q != minimized_m2.Q or \
minimzed_m1.sigma != minimized_m2.sigma or \
minimized_m1.q0 != minimized_m2.q0 or \
minimized_m1.F != minimized_m2.F:
return False
m2_delta_includes_m1_delta = delta_subseteq(minimized_m1.q0, \
minimized_m1.sigma, \
minimized_m1.delta, \
minimized_m2.delta)
m1_delta_includes_m2_delta = delta_subseteq(minimized_m2.q0, \
minimized_m2.sigma, \
minimized_m2.delta, \
minimized_m1.delta)
return m2_delta_includes_m1_delta and m1_delta_includes_m2_delta
\end{verbatim}
\section{Problem 4}
\label{sec:orgf8f3fbd}
We can construct a CFG:
\(S \rightarrow aSbbb | abbb\)
Which we convert to a stack machine:
\begin{center}
\begin{tabular}{lll}
read & pop & push\\[0pt]
\(\epsilon\) & S & aSbbb\\[0pt]
\(\epsilon\) & S & abbb\\[0pt]
a & a & \(\epsilon\)\\[0pt]
b & b & \(\epsilon\)\\[0pt]
\end{tabular}
\end{center}
\(M = (\{a, b, S\}, \{a, b\}, S, \delta)\)
where
\begin{enumerate}
\item \(\delta(\epsilon, S) = \{aSbbb, abbb\}\)
\item \(\delta(a, a) = \{ \epsilon \}\)
\item \(\delta(b, b) = \{ \epsilon \}\)
\end{enumerate}
\section{Problem 5}
\label{sec:org0f801f2}
\begin{enumerate}
\item \(S \rightarrow 0 | 0T | 1T\)
\item \(T \rightarrow 1S | 0S\)
\end{enumerate}
Is a right linear grammar, and is thus regular.
\section{Problem 6}
\label{sec:org690d7be}
\subsection{One}
\label{sec:orgc0da8de}
\begin{center}
\includegraphics[width=200px]{./img/p6.png}
\end{center}
\begin{itemize}
\item \(Q = \{p_0, p_1\}\)
\item \(F = \{p_1\}\)
\item \(\Sigma = \{1\}\)
\item \(S = p_0\)
\item \(\delta(p_0, 1) = p_1\)
\item \(\delta(p_1, 1) = p_0\)
\end{itemize}
\subsection{Two}
\label{sec:org0e05810}
\begin{center}
\includegraphics[width=200px]{./img/6b.png}
\end{center}
\begin{itemize}
\item \(Q = \{p_0, p_1, p_2, p_3, p_4, p_5\}\)
\item \(F = \{p_2, p_4, p_6\}\)
\item \(\Sigma = \{a, b\}\)
\item \(S = p_0\)
\item \(\delta(p_0, a) = p_1\)
\item \(\delta(p_0, b) = p_3\)
\item \(\delta(p_1, a) = p_6\)
\item \(\delta(p_1, b) = p_2\)
\item \(\delta(p_2, b) = p_5\)
\item \(\delta(p_5, b) = p_2\)
\item \(\delta(p_3, b) = p_4\)
\item \(\delta(p_4, b) = p_3\)
\item \(\delta(p_3, a) = \delta(p_4, a) = \delta(p_2, a) = \delta(p_5, a) = \emptyset\)
\end{itemize}
\section{Problem 7}
\label{sec:org4149a63}
\begin{center}
\includegraphics[width=200px]{./img/7.png}
\end{center}
Because the magnitude of each element in the range of \(\delta\) is 1 then, intuitively, if we follow
the subset construction algorithm with queue optimization we will only end up with new states
identical to the ones present in the current NFA (i.e. we will visit no elements of the powerset
whose magnitude is greater than one also).
Thus the DFA is:
\begin{itemize}
\item \(Q = \{q_0, q_1, q_2, q_3, q_4\}\)
\item \(F = \{q_4\}\)
\item \(\Sigma = \{a, b\}\)
\item \(S = q_0\)
\item \(\delta(q_0, a) = q_1\)
\item \(\delta(p_1, a) = q_2\)
\item \(\delta(q_2, a) = q_2\)
\item \(\delta(q_2, b) = q_3\)
\item \(\delta(q_3, b) = q_4\)
\item \(\delta(p_4, b) = q_4\)
\item \(\delta(q_0, b) = \delta(q_1, b) = \delta(q_3, a) = \delta(p_4, a) = \emptyset\)
\end{itemize}
\end{document}
|
