Theoretical Aspects of Lexical Analysis/Exercise 6: Difference between revisions
From Wiki**3
| Line 43: | Line 43: | ||
== DFA == | == DFA == | ||
Determination table for the above NFA | {{CollapsedCode|Determination table for the above NFA| | ||
{| 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 131: | Line 130: | ||
|- | |- | ||
|} | |} | ||
}} | |||
{{CollapsedCode|Graphical representation of the DFA| | |||
<graph> | <graph> | ||
digraph dfa { | digraph dfa { | ||
| Line 150: | Line 149: | ||
} | } | ||
</graph> | </graph> | ||
}} | |||
{{CollapsedCode|DFA minimization tree| | |||
Note that before considering transition behavior, states are split according to the token they recognize. | |||
<graph> | <graph> | ||
| Line 173: | Line 174: | ||
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 == | ||
Revision as of 10:34, 5 March 2016
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 = { aa, aaaa, a|b}, input string = aaabaaaaa
NFA
The following is the result of applying Thompson's algorithm.
| NFA built by Thompson's algorithm |
|---|
| b)*abb(a |
DFA
| Determination table for the above NFA |
|---|
|
{ |
| Graphical representation of the DFA |
|---|
| b)*abb(a |
| DFA minimization tree |
|---|
| {{{2}}} |
Input Analysis
| 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).