|
|
| (3 intermediate revisions by the same user not shown) |
| Line 3: |
Line 3: |
| * <nowiki>G = { a*, ba*, a*|b }</nowiki>, input string = aababb | | * <nowiki>G = { a*, ba*, a*|b }</nowiki>, input string = aababb |
|
| |
|
| == NFA == | | == Solution == |
|
| |
|
| The following is the result of applying Thompson's algorithm.
| | {{CollapsedCode|Solução completa| |
| <!--
| | [[Image:asbasasob1.jpg]] |
| State '''4''' recognizes the first expression (token '''T1'''); state '''9''' recognizes token '''T2'''; and state '''17''' recognizes token '''T3'''.
| | [[Image:asbasasob2.jpg]] |
| | }} |
|
| |
|
| <graph>
| | [[category:Compiladores]] |
| digraph nfa {
| | [[category:Ensino]] |
| { node [shape=circle style=invis] s }
| |
| rankdir=LR; ratio=0.5
| |
| node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 4 9 17
| |
| node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
| |
|
| |
|
| s -> 0
| |
|
| |
| 0 -> 1
| |
| 1 -> 2
| |
| 1 -> 4
| |
| 2 -> 3 [label="a",fontsize=10]
| |
| 3 -> 2
| |
| 3 -> 4
| |
|
| |
| 0 -> 5
| |
| 5 -> 6 [label="b",fontsize=10]
| |
| 6 -> 7
| |
| 6 -> 9
| |
| 7 -> 8 [label="a",fontsize=10]
| |
| 8 -> 7
| |
| 8 -> 9
| |
|
| |
| 0 -> 10
| |
| 10 -> 11
| |
| 10 -> 13
| |
| 11 -> 12 [label="a",fontsize=10]
| |
| 12 -> 17
| |
| 13 -> 14
| |
| 13 -> 16
| |
| 14 -> 15 [label="b",fontsize=10]
| |
| 15 -> 14
| |
| 15 -> 16
| |
| 16 -> 17
| |
| fontsize=10
| |
| }
| |
| </graph>
| |
| -->
| |
| == DFA ==
| |
|
| |
| Determination table for the above NFA:
| |
| <!--
| |
| {| cellspacing="2"
| |
| ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub>
| |
| ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | α∈Σ
| |
| ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | move(I<sub>n</sub>, α)
| |
| ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | ε-closure(move(I<sub>n</sub>, α))
| |
| ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n+1</sub> = ε-closure(move(I<sub>n</sub>, α))
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | -
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | -
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 0
| |
| ! style="font-weight: normal; align: left; background: #ffffcc;" | 0, 1, 2, '''4''', 5, 10, 11, 13, 14, 16, '''17'''
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | '''0''' (T1)
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | a
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 3, 12
| |
| ! style="font-weight: normal; align: left; background: #e6e6e6;" | 2, 3, '''4''', 12, '''17'''
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''1''' (T1)
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | b
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 6, 15
| |
| ! style="font-weight: normal; align: left; background: #e6e6e6;" | 6, 7, '''9''', 14, 15, 16, '''17'''
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''2''' (T2)
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 1
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | a
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 3
| |
| ! style="font-weight: normal; align: left; background: #ffffcc;" | 2, 3, '''4'''
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | '''3''' (T1)
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 1
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | b
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | -
| |
| ! style="font-weight: normal; align: left; background: #ffffcc;" | -
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | -
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | a
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 8
| |
| ! style="font-weight: normal; align: left; background: #e6e6e6;" | 7, 8, '''9'''
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''4''' (T2)
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | b
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 15
| |
| ! style="font-weight: normal; align: left; background: #e6e6e6;" | 14, 15, 16, '''17'''
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''5''' (T3)
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 3
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | a
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 3
| |
| ! style="font-weight: normal; align: left; background: #ffffcc;" | 2, 3, '''4'''
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | '''3''' (T1)
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 3
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | b
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | -
| |
| ! style="font-weight: normal; align: left; background: #ffffcc;" | -
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | -
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | a
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 8
| |
| ! style="font-weight: normal; align: left; background: #e6e6e6;" | 7, 8, '''9'''
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''4''' (T2)
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | b
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | -
| |
| ! style="font-weight: normal; align: left; background: #e6e6e6;" | -
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | -
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 5
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | a
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | -
| |
| ! style="font-weight: normal; align: left; background: #ffffcc;" | -
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | -
| |
| |-
| |
| ! 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;" | 15
| |
| ! style="font-weight: normal; align: left; background: #ffffcc;" | 14, 15, 16, '''17'''
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | '''5''' (T3)
| |
| |}
| |
| -->
| |
| Graphically, the DFA is represented as follows:
| |
| <!--
| |
| <graph>
| |
| digraph dfa {
| |
| { node [shape=circle style=invis] s }
| |
| rankdir=LR; ratio=0.5
| |
| node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 1 2 3 4 5
| |
| node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
| |
| s -> 0
| |
| 0 -> 1 [label="a",fontsize=10]
| |
| 0 -> 2 [label="b",fontsize=10]
| |
| 1 -> 3 [label="a",fontsize=10]
| |
| 2 -> 4 [label="a",fontsize=10]
| |
| 2 -> 5 [label="b",fontsize=10]
| |
| 3 -> 3 [label="a",fontsize=10]
| |
| 4 -> 4 [label="a",fontsize=10]
| |
| 5 -> 5 [label="b",fontsize=10]
| |
| fontsize=10
| |
| }
| |
| </graph>
| |
| -->
| |
| The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize.
| |
| <!--
| |
| <graph>
| |
| digraph mintree {
| |
| node [shape=none,fixedsize=true,width=0.3,fontsize=10]
| |
| "{0, 1, 2, 3, 4, 5}" -> "{}" [label="NF",fontsize=10]
| |
| "{0, 1, 2, 3, 4, 5}" -> "{0, 1, 2, 3, 4, 5} " [label=" F",fontsize=10]
| |
| "{0, 1, 2, 3, 4, 5} " -> "{0, 1, 3}" [label=" T1",fontsize=10]
| |
| "{0, 1, 2, 3, 4, 5} " -> "{2, 4}" [label=" T2",fontsize=10]
| |
| "{0, 1, 2, 3, 4, 5} " -> "{5}" [label=" T3",fontsize=10]
| |
| "{0, 1, 3}" -> "{0}" //[label=" b",fontsize=10]
| |
| "{0, 1, 3}" -> "{1,3}" [label=" b",fontsize=10]
| |
| "{2, 4}" -> "{2}" //[label=" b",fontsize=10]
| |
| "{2, 4}" -> "{4}" [label=" b",fontsize=10]
| |
| fontsize=10
| |
| //label="Minimization tree"
| |
| }
| |
| </graph>
| |
|
| |
| 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.
| |
|
| |
| <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 5
| |
| 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="a",fontsize=10]
| |
| 4 -> 4 [label="a",fontsize=10]
| |
| 2 -> 5 [label="b",fontsize=10]
| |
| 5 -> 5 [label="b",fontsize=10]
| |
| fontsize=10
| |
| }
| |
| </graph>
| |
| -->
| |
| == Input Analysis ==
| |
| <!--
| |
| {| cellspacing="2"
| |
| ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub>
| |
| ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | Input
| |
| ! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n+1</sub> / Token
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 0
| |
| ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aababb$</tt>
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 13
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 13
| |
| ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>ababb$</tt>
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 13
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 13
| |
| ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>babb$</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>babb$</tt>
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
| |
| |-
| |
| ! 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; align: center; background: #e6e6e6;" | 4
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
| |
| ! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>bb$</tt>
| |
| ! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T2''' (ba)
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 0
| |
| ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>bb$</tt>
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 2
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 2
| |
| ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>b$</tt>
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 5
| |
| |-
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | 5
| |
| ! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt>
| |
| ! style="font-weight: normal; align: center; background: #ffffcc;" | '''T3''' (bb)
| |
| |}
| |
|
| |
| The input string ''aababb'' is, after 9 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aa''), '''T2''' (''ba''), and '''T3''' (''bb'').
| |
| -->
| |
|
| |
| [[category:Teaching]]
| |
| [[category:Compilers]]
| |
| [[en:Theoretical Aspects of Lexical Analysis]] | | [[en:Theoretical Aspects of Lexical Analysis]] |
