-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsipser.html
490 lines (478 loc) · 35.4 KB
/
sipser.html
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
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>sipser computation</title>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4.3.1/dist/css/bootstrap.min.css" integrity="sha384-ggOyR0iXCbMQv3Xipma34MD+dH/1fQ784/j6cY/iJTQUOhcWr7x9JvoRxT2MZw1T" crossorigin="anonymous">
<link rel="stylesheet" href="style.css">
<link rel="preconnect" href="https://fonts.googleapis.com">
<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
<link href="https://fonts.googleapis.com/css2?family=Noto+Sans+JP&display=swap" rel="stylesheet">
</head>
<body>
<div class="topnav">
<a id = "sipser" class = "btn" href = "index.html" >back</a>
</div>
<div class = "sipser-container">
<h1 class = "sipser-title">Sipser Computation Theory</h1>
<div class = "sipser-list">
<div class = "cfl">
<div class= "dcfl">
<div class = "reg">
<!-- REGULAR LANGUAGE -->
<div class = "sipser-obj">
<h1 class = "sipser-title" style = "color: #5B527A; -webkit-text-stroke-color: #5B527A;">Regular</h1>
<div class = "sipser-obj-content">
<p class = "title"><strong>What is a Regular Language?</strong></p>
<div class = "sipser-def">
<p class = "def-title">sipser gospels <strong>1.16</strong></p>
<div class = "def-content">
<p>A language is called a <strong><em>regular language </em></strong>
if some finite automaton recognizes it.</p>
</div>
</div>
<br>
<p> What languages aren't regular?</p>
<br>
<p class = "title"><strong>The Pumping Lemma for Regular Languages</strong></p>
<div class = "sipser-def">
<p class = "def-title" style = "width: 150px;">sipser lemma</p>
<div class = "def-content">
<p>
If <em>A</em> is a regular language, then there is a number <em>p</em> (the pumping length) where if <em>s</em> is any string in
<em>A</em> of length at least <em>p</em>, then <em>s</em> may be divided into three pieces,
<em>s</em> = <em>x</em><em>y</em><em>z</em>, satisfying the following conditions:
</p>
<ol type = "1">
<li>for each <span style="font-size: 26px;">𝑖</span> <span style="font-size: 15px;">≥</span> 0, <em>x</em><em>y</em><sup style="right:-3px;font-size:16px;">𝑖</sup><em>z</em>
∊ <em>A</em>,
</li>
<li>
|<em>y</em> | > 0,
</li>
<li>|<em>x</em><em>y</em> | <span style="font-size: 15px;">≤</span> <em>p</em>.</li>
</ol>
</div>
</div>
<br>
<div class = "closure">
<div class = "closure-obj">
<p class = "title">e.g.</p>
<div class = "closure-content">
<p>
let <em>B</em> be the language {0<sup><em>n</em></sup> 1<sup><em>n</em></sup> | <em>n</em> <span style="font-size: 15px;">≥</span> 0},
<br>
and let <em>p</em>, the pumping length, be the number of states of the machine that recognizes <em>B</em>.
</p>
<br>
<ol start="1">
<li>
Choose a string that is in the language <em>B</em>, and that satisfies the conditions set above,
</li>
</ol>
<br>
<p class = "center">
let <em>s</em> be the string 0<sup><em>p</em></sup> 1<sup><em>p</em></sup>
</p>
<br>
<ol start="2">
<li>
Split the string into <em>x</em><em>y</em><em>z</em>,
</li>
</ol>
<br>
<p class ="center">
we can set <em>x</em> to 0,<br>
and set <em>z</em> to 1,<br>
but with <em>y</em>,
</p>
<br>
<p>
if we choose either 0 or 1 to be repeated, the string <em>xyyz</em> (0111 or 0001) is no longer a member of the
language,
</p>
<br>
<p>
Since this violates condition 1 of the lemma, the language {0<sup><em>n</em></sup> 1<sup><em>n</em></sup> | <em>n</em> <span style="font-size: 15px;">≥</span> 0}
is <strong><mark>not regular</mark></strong>
</p>
<br>
<p>
If this language was regular it would be able to repeat the middle section of the string without violating condition 1.
</p>
</div>
</div>
</div>
</div>
</div>
<!-- DFA -->
<div class = "sipser-obj">
<h1 class = "sipser-title">DFA</h1>
<div class = "sipser-obj-content">
<p class = "left title">A <strong><em>deterministic finite automaton</em></strong> is a <strong>5-tuple</strong>
<br><span style="font-size:35px">(<em>Q</em>, Σ, δ, <em>q</em><sub>0</sub>, <em>F</em> )</span></p>
<br>
<ol type="1">
<li><em>Q</em> is a finite set of <em>states</em></li>
<li>Σ is a finite <em>alphabet</em></li>
<li>δ : <em>Q</em> x Σ → <em>Q</em> is the <em>transition function</em></li>
<li><em>q</em><sub>0</sub> ∊ <em>Q</em> is the <em> start state</em></li>
<li><em>F</em> <span style="font-size:15px">⊆</span> <em>Q </em> is the <em>set of accept states</em></li>
</ol>
<br>
<p style="font-size:25px"><mark><strong>Every state of a DFA always has
<span style = "color:red; -webkit-text-stroke-color: red; " > exactly one </span> exiting transition arrow
<br>for each symbol in the alphabet</strong></mark></p>
<br>
<div class = "content-img">
<p><b>simple DFA e.g.</b></p>
<img src = "assets/dfaeg.png"/>
</div>
</div>
<!-- END DFA -->
<br><br>
<!-- NFA -->
<div class = "sipser-obj">
<h1 class = "sipser-title">NFA</h1>
<div class = "sipser-obj-content">
<p class = "left title">A <strong><em>nondeterministic finite automaton</em></strong> is a <strong>5-tuple</strong>
<br><span style="font-size:35px">(<em>Q</em>, Σ, δ, <em>q</em><sub>0</sub>, <em>F</em> )</span>,</p>
<br>
<ol type="1">
<li><em>Q</em> is a finite set of <em>states</em></li>
<li>Σ is a finite <em>alphabet</em></li>
<li>δ : <em>Q</em> x Σ<sub>ε</sub> → <em>P</em> (<em>Q</em> ) is the <em>transition function</em></li>
<li><em>q</em><sub>0</sub> ∊ <em>Q</em> is the <em> start state</em></li>
<li><em>F</em> <span style="font-size:15px">⊆</span> <em>Q </em> is the <em>set of accept states</em></li>
</ol>
<br>
<div class = "content-img">
<p><b>simple NFA e.g.</b></p>
<img src = "assets/nfaeg.png"/>
</div>
<br>
<p>
The symbol that was added to the alphabet in the transition function, and the symbol on the picture above is<br>
<br>
<span style = "font-size: 40px;"><mark>epsilon ε</mark></span>
<br>
<br>
Nondeterminism brings with it epsilon, which represents an empty string.<br><br>
Not to be confused with Ø which represents the lack of a string.<br><br>
Epsilon transitions allow the machine to switch states without reading any input.
</p>
</div>
</div>
<!-- END NFA -->
</div>
<div class = "sipser-obj">
<h1 class = "sipser-title">Regular Operations</h1>
<div class = "sipser-obj-content">
<div class = "sipser-def">
<p class = "def-title">sipser gospels <strong>1.23</strong></p>
<div class = "def-content">
<p>
Let A and B be languages. We define the regular operations <strong>union</strong>,
<strong>concatenation</strong>, and <strong>star </strong> as follows:</p>
<ul>
<li><strong>Union:</strong> <em> A</em> ∪ <em>B</em> = { 𝑥 | 𝑥 ∊ <em>A </em> or 𝑥 ∊ <em>B</em> }. </li>
<li><strong>Concatenation:</strong> <em> A</em>
<span style = "font-size: 10px;position: relative; top: -4px;" >○</span>
<em>B</em> = { 𝑥𝑦 | 𝑥 ∊ <em>A </em> and 𝑦 ∊ <em>B</em> }. </li>
<li><strong>Star:</strong> <em> A</em> <sup style = "font-size: 20px;left: -5px; top: -7px;">∗</sup>
= { 𝑥<sub style = "font-size: 13px;">1 </sub>𝑥<sub style = "font-size: 13px;">2</sub>
<span style = "position: relative; top:-2px">…</span> 𝑥<sub style = "font-size: 16px;">𝑘 </sub>
| 𝑘 <span style = "font-size: 13px;">≥</span> 0 and each 𝑥<sub style = "font-size: 16px;">𝑖 </sub>
∊ <em>A</em> }. </li>
</ul>
</p>
</div>
</div>
<p class = "title"><strong>Closure under Regular Operations:</strong></p>
<div class = "closure">
<div class = "closure-obj">
<p class = "title"><strong>Union -</strong></p>
<p class = "closure-content">
Assuming we are taking the union of machines <b>M<sub>1</sub></b> and <b>M<sub>2</sub></b>,
</p>
</div>
<div class = "closure-obj">
<p class = "title"><strong>Concatenation -</strong></p>
<p class = "closure-content">
Assuming we are concatenating strings of the languages for machines <b>M<sub>1</sub></b> and <b>M<sub>2</sub></b>,
</p>
</div>
<div class = "closure-obj">
<p class = "title"><strong>Star -</strong></p>
<p class = "closure-content">
Assuming we are taking the Kleene star of the language for machine <b>M<sub>1</sub></b>,
</p>
</div>
</div>
</div>
</div>
<!-- REGEX -->
<div class = "sipser-obj">
<h1 class = "sipser-title">regex</h1>
<div class = "sipser-obj-content">
<div class = "sipser-def">
<p class = "def-title">sipser gospels <strong>1.23</strong></p>
<div class = "def-content">
<p>
Say that <em>R</em> is a <strong><em>regular expression</em></strong> if <em>R</em> is <br>
</p>
<ul style = "overflow: hidden;">
<li><strong>1.</strong> 𝑎 for some 𝑎 in the alphabet Σ,</li>
<li><strong>2.</strong> ε</li>
<li><strong>3.</strong> Ø</li>
<li><strong>4.</strong> (<em>R</em><sub>1</sub> ⋃ <em>R</em><sub>2</sub>),
where <em>R</em><sub>1</sub> and <em>R</em><sub>2</sub> are regular expressions,
</li>
<li><strong>5.</strong> (<em>R</em><sub>1</sub>
<span style = "font-size: 10px;position: relative; top: -4px;" >○</span>
<em>R</em><sub>2</sub>),
where <em>R</em><sub>1</sub> and <em>R</em><sub>2</sub> are regular expressions,
</li>
<li><strong>6.</strong> (<em>R</em><sub>1</sub>
<sup style = "font-size: 20px;left: -5px; top: -7px;">∗</sup>),
where <em>R</em><sub>1</sub> is a regular expression.
</li>
</ul>
<p>
In items 1 and 2, the regular expressions 𝑎 and ε represent the
languages {𝑎} and {ε}, respectively. In item 3, the regular expression
Ø represents the empty language.
</p>
</div>
</div>
<br>
<p class = "title">
<mark><strong>
Don't confuse the regular expressions ε and Ø!
</strong></mark>
</p>
<br>
<div class = "content-img">
<img src = "assets/regexeg.png"/>
</div>
<p>An example of a regular expression whos value represents a language that consists of
all possible strings of 0's and 1's.</p>
</div>
</div>
<!-- ENDREGEX -->
</div>
<!-- END REGULAR LANGUAGE -->
<!-- DETERMISTIC CONTEXT FREE LANGUAGE -->
<div class = "sipser-obj">
<h1 class = "sipser-title" style = "color: #525D7A; -webkit-text-stroke-color: #525D7A;">Deterministic Context Free</h1>
</div>
<!-- DCFG -->
<!-- END DCFG -->
<!-- DPDA-->
<!-- END DPDA-->
</div>
<!-- END DETERMISTIC CONTEXT FREE LANGUAGE -->
<!-- CONTEXT FREE LANGUAGE -->
<div class = "sipser-obj">
<h1 class = "sipser-title" style = "color: #52717A; -webkit-text-stroke-color: #52717A;">Context Free</h1>
<div class = "sipser-obj-content">
<p class = "title"><strong>What is a Context Free Language?</strong></p>
<div class = "sipser-def">
<p class = "def-title">andrew gospels <strong>1.01</strong></p>
<div class = "def-content">
<p>A language is called a <strong><em>context free language </em></strong>
if some context free grammar or pushdown automaton recognizes it.</p>
</div>
</div>
<br>
<p>
With regular languages, we looked at the language
{0<sup><em>n</em></sup> 1<sup><em>n</em></sup> | <em>n</em> <span style="font-size: 15px;">≥</span> 0}
and determined it was not regular.
</p>
<br>
<p>
Using the newfound computing power of context free languages we find that there is a context free grammar up to the task,
<br>
<br>
<em>S</em> → <em>S<sub>1</sub></em> | <em>S<sub>2</sub></em><br>
<em>S<sub>1</sub></em> → 0 <em>S<sub>1</sub></em> 1 | ε<br>
<em>S<sub>2</sub></em> → 1 <em>S<sub>2</sub></em> 0 | ε<br>
<br>
Therefore the language {0<sup><em>n</em></sup> 1<sup><em>n</em></sup> | <em>n</em> <span style="font-size: 15px;">≥</span> 0}
is <strong><mark>context free</mark></strong> but,
</p>
<br>
<p> What languages aren't context free?</p>
<br>
<p class = "title"><strong>The Pumping Lemma for Context Free Languages</strong></p>
<div class = "sipser-def">
<p class = "def-title" style = "width: 150px;">sipser lemma</p>
<div class = "def-content">
<p>
If <em>A</em> is a context free language, then there is a number <em>p</em> (the pumping length) where if <em>s</em> is any string in
<em>A</em> of length at least <em>p</em>, then <em>s</em> may be divided into <strong><mark>five</mark></strong> pieces,
<em>s</em> = <em>uvxyz</em>, satisfying the following conditions:
</p>
<ol type = "1">
<li>for each <span style="font-size: 26px;">𝑖</span> <span style="font-size: 15px;">≥</span> 0,
<em>uv<sup style="right:-3px;font-size:16px;">𝑖</sup>xy<sup style="right:-3px;font-size:16px;">𝑖</sup>z</em>
∊ <em>A</em>,
</li>
<li>
|<em>vy</em> | > 0,
</li>
<li>|<em>vxy</em> | <span style="font-size: 15px;">≤</span> <em>p</em>.</li>
</ol>
</div>
</div>
<br>
<div class = "closure">
<div class = "closure-obj">
<p class = "title">e.g.</p>
<div class = "closure-content">
<p>
let <em>B</em> be the language {0<sup><em>n</em></sup> 1<sup><em>n</em></sup> 2<sup><em>n</em></sup> | <em>n</em> <span style="font-size: 15px;">≥</span> 0},
</p>
<br>
<ol start="1">
<li>
Choose a string that is in the language <em>B</em>, and that satisfies the conditions set above,
</li>
</ol>
<br>
<p class = "center">
let <em>s</em> be the string 0<sup><em>p</em></sup> 1<sup><em>p</em></sup> 2<sup><em>p</em></sup>
</p>
<br>
<ol start="2">
<li>
Split the string into <em>uvxyz</em>,
</li>
</ol>
<br>
<p class ="center">
we find that there is no way to have the same number of 0's, 1's, and 2's without messing up the order, which matters in the language.
</p>
<br>
<p>
Since this violates condition 1 of the lemma, the language {0<sup><em>n</em></sup> 1<sup><em>n</em></sup>
2<sup><em>n</em></sup> | <em>n</em> <span style="font-size: 15px;">≥</span> 0}
is <strong><mark>not context free</mark></strong>
</p>
<br>
<p>
If this language was context free it would be able to repeat <em>v</em> and <em>y</em> of the string without violating condition 1.
</p>
</div>
</div>
</div>
</div>
</div>
<!-- CFG-->
<div class = "sipser-obj">
<h1 class = "sipser-title">CFG</h1>
<div class = "sipser-obj-content">
<p class = "left title">A <strong><em>context free grammar</em></strong> is a <strong>4-tuple</strong>
<br><span style="font-size:35px">(<em>V</em>, Σ, <em>R</em>, <em>S</em> )</span>,</p>
<br>
<ol type="1">
<li><em>V</em> is a finite set called the <strong><em>variables</em></strong>,</li>
<li>Σ is a finite set, disjoint from <em>V</em>, called the <strong><em>terminals</em></strong>,</li>
<li><em>R</em> is a finite set of <strong><em>rules</em></strong>,
with each rule being a variable pointing to a string of variables and terminals,</li>
<li><em>S</em> ∊<em>V</em> is the start variable.<br></li>
</ol>
<br>
<div class = "content-img">
<p><b>simple CFG e.g.</b></p>
<img src = "assets/cfgeg.png"/>
</div>
<p style="font-size: 20px;">The variable EXPR <mark><strong><em>yields</em></strong></mark> three rules → (EXPR) + (EXPR) | (EXPR) x (EXPR) | (EXPR).</p>
<br>
<div class = "sipser-def">
<p class = "def-title">sipser gospels <strong>2.7</strong></p>
<div class = "def-content">
<p>If a grammar <em>G</em> can derive a string <em>w</em> <em>ambiguously</em>,
more than one way, Grammar <em>G</em> is <strong><em>ambiguous</em></strong>.</p>
</div>
</div>
<br>
<p class = "title"> What is the simplified form?</p>
<div class = "sipser-def">
<p class = "def-title">sipser gospels <strong>2.8</strong></p>
<div class = "def-content">
<p>
A context free grammar is in <strong><em>Chomsky normal form</em></strong> if every rule is of the form,<br>
</p>
<p style="text-align: center;">
<em>A</em> → <em>BC</em><br>
<em>A</em> → <em>a</em>
</p>
<p>
where <em>a</em> is any terminal and <em>A</em>, <em>B</em>, and <em>C</em> are any variables—except that <em>B</em> and <em>C</em>
may <strong><em><mark>NOT</mark></em></strong> be the start variable. In addition, we permit the rule <em>S</em> → ε, where <em>S</em>
is the start variable.
</p>
</div>
</div>
<br>
<p>Conversion from CFG to CNF:</p>
<ol type = "1">
<li>Replace the start symbol with a new start symbol to remove cases where start symbol is on the right side,</li>
<li>Replace rules with more than two variables with containing rules to shorten each rule to two variables,</li>
<li>Eliminate rules with more than two terminals the same way,</li>
<li>Remove epsilon rules by replacing all variables that contain epsilon with their rules,</li>
<li>Remove unit rules.</li>
</ol>
</div>
</div>
<!-- END CFG-->
<!-- PDA-->
<div class = "sipser-obj">
<h1 class = "sipser-title">PDA</h1>
<div class = "sipser-obj-content">
<p class = "left title">A <strong><em>pushdown automaton</em></strong> is a <strong>6-tuple</strong>
<br><span style="font-size:35px">(<em>Q</em>, Σ, Γ, δ, <em>q</em><sub>0</sub>, <em>F</em> )</span>, </p>
<br>
<ol type="1">
<li><em>Q</em> is the set of states,</li>
<li>Σ is the input alphabet,</li>
<li>Γ is the <em>stack</em> alphabet,</li>
<li>δ: <em>Q</em> x Σ<sub>ε</sub> x Γ<sub>ε</sub> → <em>P</em> ( <em>Q</em> x Γ<sub>ε</sub> ) is the transition function,</li>
<li><em>q</em><sub>0</sub> ∊ <em>Q</em> is the <em> start state,</em></li>
<li><em>F</em> <span style="font-size:15px">⊆</span> <em>Q </em> is the <em>set of accept states.</em></li>
</ol>
<br>
<p>
The formal definition of a pushdown automaton is <strong><mark>EQUAL</mark></strong> to that of a nondeterministic finite automaton, except for the <strong>stack</strong>.<br><br>
Which means that automatically every NFA is a PDA that doesn't use the stack,<br>
This creates a relationship between the regular and context free languages, which is <strong><mark>every regular language is a context free language.</mark></strong><br><br>
A stack is valuable because for theoretical purposes we allow it to hold an <mark><strong>unlimited amount of information</strong></mark>.
</p>
<br>
<div class = "content-img">
<p><b>PDA e.g.</b></p>
<img src = "assets/pdaeg.png"/>
</div>
<br>
<p class = "title">The transition function for a PDA takes the form: </p>
<p><mark><strong>read , pop → push</strong></mark></p>
<br>
<p>read being replaced with a character that from the input alphabet, Σ<sub>ε</sub>, that is read to the machine,</p>
<p>pop and push being replaced with a character from the stack alphabet, Γ<sub>ε</sub>, that can pop or push the character off or on to the stack respectively.</p>
<br>
<p>Notice how both of the alphabets in the transition function have an ε subscript,<br><br>
the reason for this is the nondeterminism of a PDA, since the PDA is able to make choices on its next move, we allow epsilon transitions where the machine may or may not
read, pop, or push at all.</p>
</div>
</div>
<!-- PDA-->
</div>
<!-- END CONTEXT FREE LANGUAGE -->
</div>
</div>
</body>
</html>