-
Notifications
You must be signed in to change notification settings - Fork 0
/
nfatodfa.html
82 lines (82 loc) · 7.41 KB
/
nfatodfa.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
<!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 a DFA</h2>
<div class="section">
<h3>Background</h3>
<p>We've seen the process of converting and ε-NFA to an NFA. This process will be extremely helpful in converting regular expressions into a state machine that's easy to use. However, NFAs may still have multiple transitions for the same input symbol from the same state, which can still make the recognition process difficult. In this section, we'll demonstrate how to convert an NFA into a DFA in order to provide a simpler recognition mechanism.</p>
</div>
<div class="section">
<h3>Example</h3>
<div class="subsection example">
<p><em>Example</em></p>
<p>The following NFA contains multiple transitions for the same input symbol from the same state:</p>
<img src="assets/examplemultipletransitionssamesymbol.png" alt="NFA with multiple transitions for the same state and symbol. This NFA contains 4 states - s0, s1, s2 and s3. s0 transitions to s1 on input symbol a. s1 transitions to s2 and s3 on input symbol b. s2 is accepting."/>
<p>This NFA recognizes the language L = {ab}. When parsing the string ab, after we encounter symbol b in state s<sub>1</sub>, we can choose to transition to state s<sub>2</sub> or s<sub>3</sub>. Since we are only looking for a single path to an accepting state, we would choose to transition to s<sub>2</sub> and accept the string.</p>
<p>As a result, this NFA is equivalent to the following DFA:</p>
<img src="assets/exampledfareduced.png" alt="Simplified DFA. This DFA contains 3 states - s0, s1 and s2. s0 transitions to s1 on input symbol a. s1 transitions to s2 on input symbol b. s2 is accepting."/>
</div>
</div>
<div class="section">
<h3>More complex example</h3>
<div class="subsection example">
<p><em>Example</em></p>
<p>The following is an example of an NFA that is significantly more complex:</p>
<img src="assets/examplecomplexmultipletransitionssamesymbol.png" alt="Complex NFA with multiple transitions for the same symbol and state. This NFA contains 6 states - s0 through s5. s0 transitions to s1 on input symbol a. s1 transitions to s0 and s3 on input symbol b. s1 transitions to s2 on input symbol c. s3 transitions to s4 on input symbol a. s4 transitions to s5 on input symbol c. s2 is accepting."/>
<p>Here, it's less clear how to reduce this to a DFA.</p>
<p>Now, consider the transitions from s<sub>1</sub> for input symbol b. The possible set of next states is: {s<sub>0</sub>, s<sub>3</sub>}.</p>
<p>Since we only need to find a single path for a certain input string to an accepting state, we would continue the process of considering the set of all possible next states as we iterate through the input string.</p>
<p>For example, if we process input characters a then b, our possible set of states is {s<sub>0</sub>, s<sub>3</sub>}. On subsequent input symbol a, the next set of possible states is: {s<sub>1</sub>, s<sub>4</sub>}.</p>
</div>
</div>
<div class="section">
<h3>Reduction process</h3>
<p>To outline the reduction process, for our set of states S, we must consider the power set of S.</p>
<div class="subsection definition">
<p><em>Defintion</em></p>
<p>Given our set of states</p>
<p>S = {s<sub>0</sub>, s<sub>1</sub>, ..., s<sub>n - 1</sub>}</p>
<p>The power set of S is defined as:</p>
<p>P(S) = {{}, {s<sub>0</sub>}, ..., {s<sub>n - 1</sub>}, {s<sub>0</sub>, s<sub>1</sub>}, {s<sub>0</sub>, s<sub>2</sub>}, ..., {s<sub>n - 2</sub>, s<sub>n - 1</sub>}, {s<sub>0</sub>, s<sub>1</sub>, s<sub>2</sub>}, ..., {s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>n - 1</sub>}}</p>
</div>
<p>Informally, the power set of S is the set containg all possible subsets of S.</p>
<p>Since, as illustated above, we need to consider combinations of possible states, we will construct a new set of states in our DFA which maps to some combination of states from our DFA. Specifically, these combinations map to some element of the power set of S, P(S).</p>
<p>Our DFA's start state corresponds to the element {s<sub>0</sub>} from P(S), since this is where our parsing process starts.</p>
<p>Next, we must consider the process of working through the NFA to add additional states to our DFA.</p>
<p>We will consider a DFA state which represents some set of states from the original NFA. For each input symbol corresponding to a transition from any of the original DFA states, track all states from the DFA that would be transitioned to for that input symbol. Then, we create a new DFA state corresponding to that set of NFA states (or reuse the DFA state corresponding to that combination if one exists). Then, we can add a transition to it from the previous state.</p>
<p>We set our new DFA state to accepting if at least one of the NFA states it was derived from is accepting.</p>
</div>
<div class="section">
<h3>More complex example reduced</h3>
<div class="subsection example">
<p><em>Example</em></p>
<p>Following the instructions above, our complex NFA can can be reduced to the following DFA:</p>
<img src="assets/examplecomplexdfareduced.png" alt="Simplified DFA. This DFA contains 6 states, each of which represents some set of states from the DFA. State with set s0 transitions to state with set s1 on input symbol a. State with set s1 transitions to state with set s2 on input symbol c. State with set s1 transitions to state with set s0, s3 on input symbol b. State with set s0, s3 transitions to state with set s1, s4 on input symbol a. State with set s1, s4 transitions to state with set s2, s5 on input symbol c. All new states containing s2 are accepting."/>
<p>Finally, we can re-label the states as follows:</p>
<img src="assets/examplecomplexdfareducedrelabelled.png" alt="Simplified DFA relabelled This dfa contains 6 states - s0 through s5. s0 transitions to s1 in input symbol a. s1 transitions to s2 on input symbol c. s1 transitions to s3 on input symbol b. s3 transitions to s4 on input symbol a. s4 transitions to s5 on input symbol c. s2 and s5 are accepting."/>
<p>Note that the two states whose state set from the NFA contain s<sub>2</sub> are marked as final states.</p>
</div>
</div>
<div class="section">
<h3>Conclusion</h3>
<p>In conclusion, we now have a process to convert an NFA to a DFA. Using Thompsons's construction along with the ε-NFA to NFA conversion process, we can now convert regular expressions into NFAs for straightforward recognition.</p>
</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>