(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, c }...) |
|||
| (3 intermediate revisions by the same user not shown) | |||
| Line 7: | Line 7: | ||
The following is the result of applying Thompson's algorithm. State '''8''' recognizes the first expression (token '''T1'''); state '''16''' recognizes token '''T2'''; and state '''21''' recognizes token '''T3'''. | The following is the result of applying Thompson's algorithm. State '''8''' recognizes the first expression (token '''T1'''); state '''16''' recognizes token '''T2'''; and state '''21''' recognizes token '''T3'''. | ||
| − | < | + | <dot-hack> |
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 50: | Line 50: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
| − | </ | + | </dot-hack> |
== DFA == | == DFA == | ||
| Line 167: | Line 167: | ||
! style="font-weight: normal; align: center; background: #ffffcc;" | 5 | ! style="font-weight: normal; align: center; background: #ffffcc;" | 5 | ||
! style="font-weight: normal; align: center; background: #ffffcc;" | b | ! style="font-weight: normal; align: center; background: #ffffcc;" | b | ||
| − | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 14 |
| − | ! style="font-weight: normal; align: left; background: #ffffcc;" | | + | ! style="font-weight: normal; align: left; background: #ffffcc;" | 13, 14, 15, '''16''' |
| − | ! style="font-weight: normal; align: center; background: #ffffcc;" | ''' | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | '''5''' (T2) |
|- | |- | ||
! style="font-weight: normal; align: center; background: #ffffcc;" | 5 | ! style="font-weight: normal; align: center; background: #ffffcc;" | 5 | ||
| Line 198: | Line 198: | ||
Graphically, the DFA is represented as follows: | Graphically, the DFA is represented as follows: | ||
| − | < | + | <dot-hack> |
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 216: | Line 216: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
| − | </ | + | </dot-hack> |
The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize. | The minimization tree is as follows. 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] | ||
| Line 229: | Line 229: | ||
"{0, 1, 2, 3, 4, 5, 6} " -> "{6}" [label=" T3",fontsize=10] | "{0, 1, 2, 3, 4, 5, 6} " -> "{6}" [label=" T3",fontsize=10] | ||
"{0, 1, 3, 4}" -> "{0, 1, 4}" [label=" a",fontsize=10] | "{0, 1, 3, 4}" -> "{0, 1, 4}" [label=" a",fontsize=10] | ||
| − | "{0, 1, 3, 4}" -> "{3}" | + | "{0, 1, 3, 4}" -> "{3}" |
"{2, 5}" -> "{2}" [label=" c",fontsize=10] | "{2, 5}" -> "{2}" [label=" c",fontsize=10] | ||
| − | "{2, 5}" -> "{5}" | + | "{2, 5}" -> "{5}" |
"{0, 1, 4}" -> "{0}" [label=" b",fontsize=10] | "{0, 1, 4}" -> "{0}" [label=" b",fontsize=10] | ||
| − | "{0, 1, 4}" -> "{1, 4}" | + | "{0, 1, 4}" -> "{1, 4}" |
"{1, 4}" -> "{1, 4} " [label=" a, b, c",fontsize=10] | "{1, 4}" -> "{1, 4} " [label=" a, b, c",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
| − | |||
} | } | ||
| − | </ | + | </dot-hack> |
Given the minimization tree, the final minimal DFA is as follows. | Given the minimization tree, the final minimal DFA is as follows. | ||
| − | < | + | <dot-hack> |
digraph dfa { | digraph dfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 259: | Line 258: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
| − | </ | + | </dot-hack> |
== Input Analysis == | == Input Analysis == | ||
| Line 322: | Line 321: | ||
|} | |} | ||
| − | The input string ''aaabcacc'' is, after 13 steps, split into | + | The input string ''aaabcacc'' is, after 13 steps, split into five tokens: '''T1''' (corresponding to lexeme ''aaa''), '''T3''' (''bc''), '''T1''' (''a''), '''T1''' (''c''), '''T1''' (''c''). |
| + | |||
| + | [[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, c }. Indicate the number of processing steps for the given input string.
The following is the result of applying Thompson's algorithm. State 8 recognizes the first expression (token T1); state 16 recognizes token T2; and state 21 recognizes token T3.
Determination table for the above NFA:
| In | α∈Σ | move(In, α) | ε-closure(move(In, α)) | In+1 = ε-closure(move(In, α)) |
|---|---|---|---|---|
| - | - | 0 | 0, 1, 2, 3, 5, 6, 8, 9, 10, 12, 13, 15, 16, 17 | 0 (T1) |
| 0 | a | 4, 11 | 3, 4, 5, 8, 11, 16 | 1 (T1) |
| 0 | b | 14, 18 | 13, 14, 15, 16, 18, 19, 21 | 2 (T2) |
| 0 | c | 7 | 7, 8 | 3 (T1) |
| 1 | a | 4 | 3, 4, 5, 8 | 4 (T1) |
| 1 | b | - | - | - |
| 1 | c | - | - | - |
| 2 | a | - | - | - |
| 2 | b | 14 | 13, 14, 15, 16 | 5 (T2) |
| 2 | c | 20 | 19, 20, 21 | 6 (T3) |
| 3 | a | - | - | - |
| 3 | b | - | - | - |
| 3 | c | - | - | - |
| 4 | a | 4 | 3, 4, 5, 8 | 4 (T1) |
| 4 | b | - | - | - |
| 4 | c | - | - | - |
| 5 | a | - | - | - |
| 5 | b | 14 | 13, 14, 15, 16 | 5 (T2) |
| 5 | c | - | - | - |
| 6 | a | - | - | - |
| 6 | b | - | - | - |
| 6 | c | 20 | 19, 20, 21 | 6 (T3) |
Graphically, the DFA is represented as follows:
The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize.
Given the minimization tree, the final minimal DFA is as follows.
| In | Input | In+1 / Token |
|---|---|---|
| 0 | aaabcacc$ | 14 |
| 14 | aabcacc$ | 14 |
| 14 | abcacc$ | 14 |
| 14 | bcacc$ | T1 (aaa) |
| 0 | bcacc$ | 2 |
| 2 | cacc$ | 6 |
| 6 | acc$ | T3 (bc) |
| 0 | acc$ | 14 |
| 14 | cc$ | T1 (a) |
| 0 | cc$ | 3 |
| 3 | c$ | T1 (c) |
| 0 | c$ | 3 |
| 3 | $ | T1 (c) |
The input string aaabcacc is, after 13 steps, split into five tokens: T1 (corresponding to lexeme aaa), T3 (bc), T1 (a), T1 (c), T1 (c).