(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...) |
|||
Line 166: | Line 166: | ||
The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}). | The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}). | ||
− | + | ||
− | Given the minimization tree, the final minimal DFA is | + | Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens. |
− | --> | + | |
+ | <graph> | ||
+ | digraph mindfa { | ||
+ | { node [shape=circle style=invis] s } | ||
+ | rankdir=LR; ratio=0.5 | ||
+ | node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 13 2 4 | ||
+ | node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; | ||
+ | s -> 0 | ||
+ | 0 -> 13 [label="a",fontsize=10] | ||
+ | 0 -> 2 [label="b",fontsize=10] | ||
+ | 13 -> 13 [label="a",fontsize=10] | ||
+ | 2 -> 4 [label="b",fontsize=10] | ||
+ | 4 -> 4 [label="b",fontsize=10] | ||
+ | fontsize=10 | ||
+ | } | ||
+ | </graph> | ||
+ | |||
== Input Analysis == | == Input Analysis == | ||
− | + | ||
{| cellspacing="2" | {| cellspacing="2" | ||
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub> | ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub> | ||
Line 177: | Line 193: | ||
|- | |- | ||
! 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> | + | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aababb$</tt> |
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 13 |
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 13 |
− | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt> | + | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>ababb$</tt> |
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 13 |
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 13 |
− | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt> | + | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>babb$</tt> |
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' (aa) |
|- | |- | ||
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0 | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 0 | ||
− | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt> | + | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>babb$</tt> |
− | ! style="font-weight: normal; align: center; background: #e6e6e6;" | | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2 |
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: #e6e6e6;" | | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2 |
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>abb$</tt> | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>abb$</tt> | ||
− | ! style="font-weight: normal; align: center; background: #e6e6e6;" | ''' | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T1''' (b) |
|- | |- | ||
! 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>abb$</tt> | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>abb$</tt> | ||
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 13 |
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | 13 |
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>bb$</tt> | ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>bb$</tt> | ||
− | ! style="font-weight: normal; align: center; background: #ffffcc;" | | + | ! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' (a) |
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: # | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 0 |
− | ! style="font-weight: normal; text-align: right; background: # | + | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>bb$</tt> |
− | ! style="font-weight: normal; align: center; background: # | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2 |
|- | |- | ||
− | ! style="font-weight: normal; align: center; background: # | + | ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2 |
− | ! style="font-weight: normal; text-align: right; background: # | + | ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>b$</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>$</tt> | ||
+ | ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T3''' (bb) | ||
|} | |} | ||
− | The input string '' | + | The input string ''aababb'' is, after 10 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aa''), '''T1''' (''b''), '''T1''' (''a''), and '''T3''' (''bb''). |
− | + | ||
[[category:Teaching]] | [[category:Teaching]] | ||
[[category:Compilers]] | [[category:Compilers]] | ||
[[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. State 8 recognizes the first expression (token T1); state 12 recognizes token T2; and state 20 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, 14, 15, 17, 18, 20 | 0 (T1) |
0 | a | 4, 11, 19 | 3, 4, 5, 8, 10, 11, 12, 19, 20 | 1 (T1) |
0 | b | 7, 16 | 7, 8, 15, 16, 17, 20 | 2 (T1) |
1 | a | 4, 11 | 3, 4, 5, 8, 10, 11, 12 | 3 (T1) |
1 | b | - | - | - |
2 | a | - | - | - |
2 | b | 16 | 15, 16, 17, 20 | 4 (T3) |
3 | a | 4, 11 | 3, 4, 5, 8, 10, 11, 12 | 3 (T1) |
3 | b | - | - | - |
4 | a | - | - | - |
4 | b | 16 | 15, 16, 17, 20 | 4 (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.
The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}).
Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens.
In | Input | In+1 / Token |
---|---|---|
0 | aababb$ | 13 |
13 | ababb$ | 13 |
13 | babb$ | T1 (aa) |
0 | babb$ | 2 |
2 | abb$ | T1 (b) |
0 | abb$ | 13 |
13 | bb$ | T1 (a) |
0 | bb$ | 2 |
2 | b$ | 4 |
4 | $ | T3 (bb) |
The input string aababb is, after 10 steps, split into three tokens: T1 (corresponding to lexeme aa), T1 (b), T1 (a), and T3 (bb).