(New page: __NOTOC__ Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is Σ = { a, b }. I...) |
(→DFA) |
||
(11 intermediate revisions by the same user not shown) | |||
Line 5: | Line 5: | ||
== NFA == | == NFA == | ||
− | The following is the result of applying Thompson's algorithm. State '''3''' recognizes the first expression (token '''T1'''); state '''8''' recognizes token '''T2'''; and state '''14''' recognizes token '''T3'''. | + | The following is the result of applying Thompson's algorithm. |
+ | {{CollapsedCode|NFA built by Thompson's algorithm| | ||
+ | State '''3''' recognizes the first expression (token '''T1'''); state '''8''' recognizes token '''T2'''; and state '''14''' recognizes token '''T3'''. | ||
− | < | + | <dot-hack> |
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
Line 34: | Line 36: | ||
13 -> 14 | 13 -> 14 | ||
fontsize=10 | fontsize=10 | ||
− | |||
} | } | ||
− | </ | + | </dot-hack> |
+ | }} | ||
== DFA == | == DFA == | ||
Line 129: | Line 131: | ||
|} | |} | ||
− | + | {{CollapsedCode|Graphical representation of the DFA| | |
− | + | <dot-hack> | |
− | < | ||
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
Line 144: | Line 145: | ||
4 -> 5 [label="a",fontsize=10] | 4 -> 5 [label="a",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
− | |||
} | } | ||
− | </ | + | </dot-hack> |
+ | }} | ||
− | + | {{CollapsedCode|DFA minimization tree| | |
+ | Note that before considering transition behavior, states are split according to the token they recognize. | ||
− | < | + | <dot-hack> |
digraph mintree { | digraph mintree { | ||
node [shape=none,fixedsize=true,width=0.3,fontsize=10] | node [shape=none,fixedsize=true,width=0.3,fontsize=10] | ||
− | "{0, 1, 2, 3, 4, 5}" -> "{0, 4}" [label="NF",fontsize=10] | + | "{0, 1, 2, 3, 4, 5}" -> "{0, 4}" [label=" NF",fontsize=10] |
"{0, 1, 2, 3, 4, 5}" -> "{1, 2, 3, 5}" [label=" F",fontsize=10] | "{0, 1, 2, 3, 4, 5}" -> "{1, 2, 3, 5}" [label=" F",fontsize=10] | ||
"{1, 2, 3, 5}" -> "{3}" [label=" T1",fontsize=10] | "{1, 2, 3, 5}" -> "{3}" [label=" T1",fontsize=10] | ||
"{1, 2, 3, 5}" -> "{5}" [label=" T2",fontsize=10] | "{1, 2, 3, 5}" -> "{5}" [label=" T2",fontsize=10] | ||
"{1, 2, 3, 5}" -> "{1, 2}" [label=" T3",fontsize=10] | "{1, 2, 3, 5}" -> "{1, 2}" [label=" T3",fontsize=10] | ||
− | "{1, 2}" -> "{1}" / | + | "{0, 4}" -> "{0}" /*[label=" T3",fontsize=10]*/ |
+ | "{0, 4}" -> "{4}" [label=" a",fontsize=10] | ||
+ | "{1, 2}" -> "{1}" /*[label=" T3",fontsize=10]*/ | ||
"{1, 2}" -> "{2}" [label=" a",fontsize=10] | "{1, 2}" -> "{2}" [label=" a",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
− | |||
} | } | ||
− | </ | + | </dot-hack> |
− | The tree expansion for | + | The tree expansion for sets {0, 4} and {1, 2} was only tested for "a" (sufficient). |
Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular). | Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular). | ||
+ | }} | ||
== Input Analysis == | == Input Analysis == | ||
Line 178: | Line 182: | ||
! style="font-weight: normal; align: center; background: #ffffcc;" | 0 | ! style="font-weight: normal; align: center; background: #ffffcc;" | 0 | ||
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aaabaaaaa$</tt> | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aaabaaaaa$</tt> | ||
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 1 |
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 1 | ||
+ | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aabaaaaa$</tt> | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 3 | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 3 | ||
+ | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>abaaaaa$</tt> | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 4 | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6bbaf;" | 4 | ||
+ | ! style="font-weight: normal; text-align: right; background: #e6bbaf;" | <tt>baaaaa$</tt> | ||
+ | ! style="font-weight: normal; align: center; background: #e6bbaf;" | error (backtracking) | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | 3 | ||
+ | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>abaaaaa$</tt> | ||
+ | ! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' (aa) | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 0 | ||
+ | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>abaaaaa$</tt> | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 1 | ||
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 1 | ||
+ | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>baaaaa$</tt> | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T3''' (a) | ||
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 0 |
− | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt> | + | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>baaaaa$</tt> |
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 2 |
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 2 |
− | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt> | + | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aaaaa$</tt> |
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | '''T3''' (b) |
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: #e6e6e6;" | | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 0 |
− | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>$</tt> | + | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>aaaaa$</tt> |
− | ! style="font-weight: normal; align: center; background: #e6e6e6;" | | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 1 |
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: #e6e6e6;" | | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 1 |
− | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>$</tt> | + | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>aaaa$</tt> |
− | ! style="font-weight: normal; align: center; background: #e6e6e6;" | | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 3 |
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: # | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 3 |
− | ! style="font-weight: normal; text-align: right; background: # | + | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>aaa$</tt> |
− | ! style="font-weight: normal; align: center; background: # | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 4 |
+ | |- | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 4 | ||
+ | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>aa$</tt> | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 5 | ||
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: # | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 5 |
− | ! style="font-weight: normal; text-align: right; background: # | + | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>a$</tt> |
− | ! style="font-weight: normal; align: center; background: # | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T2''' (aaaa) |
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 0 |
− | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt> | + | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>a$</tt> |
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 1 |
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 1 |
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt> | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt> | ||
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | '''T3''' (a) |
|} | |} | ||
− | + | The input string ''aaabaaaaa'' is, after 16 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aa''), '''T3''' (''a''), '''T3''' (''b''), '''T2''' (''aaaa''), and '''T3''' (''a''). | |
+ | |||
+ | [[category:Compiladores]] | ||
+ | [[category:Ensino]] | ||
− | |||
− | |||
[[en:Theoretical Aspects of Lexical Analysis]] | [[en:Theoretical Aspects of Lexical Analysis]] |
Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).
The alphabet is Σ = { a, b }. Indicate the number of processing steps for the given input string.
The following is the result of applying Thompson's algorithm.
NFA built by Thompson's algorithm |
---|
State 3 recognizes the first expression (token T1); state 8 recognizes token T2; and state 14 recognizes token T3. |
Determination table for the above NFA:
In | α∈Σ | move(In, α) | ε-closure(move(In, α)) | In+1 = ε-closure(move(In, α)) |
---|---|---|---|---|
- | - | 0 | 0, 1, 4, 9, 10, 12 | 0 |
0 | a | 2, 5, 11 | 2, 5, 11, 14 | 1 (T3) |
0 | b | 13 | 13, 14 | 2 (T3) |
1 | a | 3, 6 | 3, 6 | 3 (T1) |
1 | b | - | - | - |
2 | a | - | - | - |
2 | b | - | - | - |
3 | a | 7 | 7 | 4 |
3 | b | - | - | - |
4 | a | 8 | 8 | 5 (T2) |
4 | b | - | - | - |
5 | a | - | - | - |
5 | b | - | - | - |
Graphical representation of the DFA |
---|
DFA minimization tree |
---|
Note that before considering transition behavior, states are split according to the token they recognize. The tree expansion for sets {0, 4} and {1, 2} was only tested for "a" (sufficient). Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular). |
In | Input | In+1 / Token |
---|---|---|
0 | aaabaaaaa$ | 1 |
1 | aabaaaaa$ | 3 |
3 | abaaaaa$ | 4 |
4 | baaaaa$ | error (backtracking) |
3 | abaaaaa$ | T1 (aa) |
0 | abaaaaa$ | 1 |
1 | baaaaa$ | T3 (a) |
0 | baaaaa$ | 2 |
2 | aaaaa$ | T3 (b) |
0 | aaaaa$ | 1 |
1 | aaaa$ | 3 |
3 | aaa$ | 4 |
4 | aa$ | 5 |
5 | a$ | T2 (aaaa) |
0 | a$ | 1 |
1 | $ | T3 (a) |
The input string aaabaaaaa is, after 16 steps, split into three tokens: T1 (corresponding to lexeme aa), T3 (a), T3 (b), T2 (aaaa), and T3 (a).