Theoretical Aspects of Lexical Analysis/Exercise 17: Difference between revisions
From Wiki**3
No edit summary |
No edit summary |
||
| Line 9: | Line 9: | ||
State '''4''' recognizes the first expression (token '''T1'''); state '''9''' recognizes token '''T2'''; and state '''17''' recognizes token '''T3'''. | State '''4''' recognizes the first expression (token '''T1'''); state '''9''' recognizes token '''T2'''; and state '''17''' recognizes token '''T3'''. | ||
< | <dot-hack> | ||
digraph nfa { | digraph nfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 46: | Line 46: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </dot-hack> | ||
--> | --> | ||
== DFA == | == DFA == | ||
| Line 140: | Line 140: | ||
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 157: | Line 157: | ||
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 169: | Line 169: | ||
"{0, 1, 2, 3, 4, 5} " -> "{2, 4}" [label=" T2",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, 2, 3, 4, 5} " -> "{5}" [label=" T3",fontsize=10] | ||
"{0, 1, 3}" -> "{0}" | "{0, 1, 3}" -> "{0}" | ||
"{0, 1, 3}" -> "{1,3}" [label=" b",fontsize=10] | "{0, 1, 3}" -> "{1,3}" [label=" b",fontsize=10] | ||
"{2, 4}" -> "{2}" | "{2, 4}" -> "{2}" | ||
"{2, 4}" -> "{4}" [label=" b",fontsize=10] | "{2, 4}" -> "{4}" [label=" b",fontsize=10] | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </dot-hack> | ||
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}). | ||
| Line 182: | Line 181: | ||
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. | 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. | ||
< | <dot-hack> | ||
digraph mindfa { | digraph mindfa { | ||
{ node [shape=circle style=invis] s } | { node [shape=circle style=invis] s } | ||
| Line 198: | Line 197: | ||
fontsize=10 | fontsize=10 | ||
} | } | ||
</ | </dot-hack> | ||
--> | --> | ||
== Input Analysis == | == Input Analysis == | ||
Revision as of 10:36, 12 February 2019
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.
- G = { a*, ba*, a*|b }, input string = aababb
NFA
The following is the result of applying Thompson's algorithm.
DFA
Determination table for the above NFA: 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.