-
Notifications
You must be signed in to change notification settings - Fork 0
/
epsilonnfatonfa.html
69 lines (69 loc) · 6.36 KB
/
epsilonnfatonfa.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
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="en">
<head>
<title>RIPAL: Responsive and Intuitive Parsing for the Analysis of Language</title>
<link href="styles/styles.css" rel="stylesheet" type="text/css" media="all"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
</head>
<body>
<h1>RIPAL: Responsive and Intuitive Parsing for the Analysis of Language</h1>
<h2>Pages</h2>
<nav aria-label="Pages">
<ul>
<li><a href="index.html">Home</a></li>
<li><a href="theory.html">Theory</a></li>
<li><a href="contact.html">Contact</a></li>
</ul>
</nav>
<h2>Converting an ε-NFA to an NFA</h2>
<div class="section">
<h3>Background</h3>
<p>We've seen a method for constructing ε-NFAs from regular expressions. However, using an ε-NFA to recognize a string as part of a language is tricky. We will look at a method to convert ε-NFAs to NFAs to simplify the recognition process.</p>
</div>
<div class="section">
<h3>Removing ε transitions</h3>
<div class="subsection example">
<p><em>Example</em></p>
<p>Observe the following ε-NFA:</p>
<img src="assets/exampleepsilonbeforecharactertransition.png" alt="ε-NFA with epsilon transition before character transition. This ε-NFA contains 3 states - s0, s1 and s2. s0 transitions to s1 on input symbol ε s1 transitions to s2 on input symbol a. s2 is accepting."/>
<p>This recognizes the string "a". Because the ε transition doesn't consume an input symbol, it can be simplified to the following:</p>
<img src="assets/exampleepsilonbeforecharactertransitionreduced.png" alt="Simplified NFA. This NFA contains 2 states - s0 and s1. s0 transitions to s1 on input symbol a. s1 is accepting."/>
<p>Note that we've done some state relabelling for readability after s<sub>1</sub> was eliminated from the original machine.</p>
<p>Similarly, the following ε-NFA recognizes the same language:</p>
<img src="assets/examplemultipleepsilonbeforecharactertransition.png" alt="ε-NFA with multiple epsilon transitions before character transition. This ε-NFA contains 4 states - s0, s1, s2 and s3. s0 transitions to s1 on input symbol ε s1 transitions to s2 on input symbol ε s2 transitions to s3 on input symbol a. s3 is accepting."/>
</div>
<p>When we are converting an ε-NFA into an NFA, we may encounter a sequence of ε transitions linking state s<sub>0</sub> through s<sub>n - 2</sub>, followed by a transition with input symbol σ from state s<sub>n - 2</sub> to state s<sub>n - 1</sub>. We can replace it with a two-state construction of state s<sub>0</sub> transitioning to s<sub>n - 1</sub> on input symbol σ.</p>
<p>This allows us to eliminate leading ε transitions and unnecessary states, simplifying our automaton without affecting the set of strings it accepts.</p>
</div>
<div class="section">
<h3>Making states accepting</h3>
<div class="subsection example">
<p><em>Example</em></p>
<p>Observe the following ε-NFA:</p>
<img src="assets/exampleepsilonbeforefinalstate.png" alt="ε-NFA with epsilon transition before accepting state. This ε-NFA contains 3 states - s0, s1 and s2. s0 transitions to s1 on input symbol a. s1 transitions to s2 on input symbol ε. s2 is accepting."/>
<p>This recognizes the string "a". Because the ε transition doesn't consume an input symbol, it can be simplified to the following:</p>
<img src="assets/exampleepsilonbeforefinalstatereduced.png" alt="Simplified NFA. This NFA contains 2 states - s0 and s1. s0 transitions to s1 on input symbol a. s1 is accepting."/>
<p>Similarly, the following ε-NFA recognizes the same language:</p>
<img src="assets/examplemultipleepsilonbeforefinalstate.png" alt="ε-NFA with multiple epsilon transitions before accepting state. This ε-NFA contains 4 states - s0, s1, s2 and s3. s0 transitions to s1 on input symbol a. s1 transitions to s2 on input symbol ε. s2 transitions to s3 on input symbol ε. s3 is accepting."/>
</div>
<p>When we are converting an ε-NFA into an NFA, we may encounter a sequence of ε transitions linking state s<sub>1</sub> through s<sub>n - 1</sub> following a transition with input symbol σ from state s<sub>0</sub> to state s<sub>1</sub>. We can replace it with a two-state construction of state s<sub>0</sub> transitioning to s<sub>n - 1</sub> with input symbol σ. If s<sub>n - 1</sub> was accepting in the initial construction, it will be in the new construction.</p>
<p>This allows us to remove trailing states without affecting the set of strings accepted by the automaton.</p>
</div>
<div class="section">
<h3>Summary</h3>
<p>Following the above rules, we can convert an ε-NFA into an NFA, removing all ε transitions. However, we may still have states with multiple transitions corresponding to the same symbol.</p>
</div>
<div class="section">
<h3>More complex example</h3>
<div class="subsection example">
<p><em>Example</em></p>
<img src="assets/exampleepsilonnfatoreduce.png" alt="Complex ε-NFA with multiple epsilon transitions leading to character transitions and accepting states. This ε-NFA contains 7 states - s0 through s6. s0 transitions to s1 on input symbol a. s1 transitions to s2 and s4 on input symbol ε s2 transitions to s3 on input symbol b. s4 transitions to s5 on input symbol c. s3 and s5 transition to s6 on input symbol ε s6 is accepting."/>
<p>Using the same rules as above, this can be reduced to the following NFA (which happens to, by chance, also be a DFA):</p>
<img src="assets/examplenfareduced.png" alt="Simplified NFA. This NFA contains 4 states - s0, s1, s2 and s3. s0 transitions to s1 on input sybmol a. s1 transitions to s2 on input symbol b. s1 transitions to s3 on input symbol c. s2 and s3 are accepting."/>
</div>
</div>
<hr/>
<p>GitHub Repository: <a href="https://github.com/bprollinson/ripal">https://github.com/bprollinson/ripal</a></p>
<p>Copyright © 2017 Brendan Rollinson-Lorimer</p>
</body>
</html>