Theoretical Aspects of Lexical Analysis/Exercise 4: Difference between revisions

Revision as of 07:53, 24 June 2016

Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.

The non-deterministic finite automaton (NFA), built by applying Thompson's algorithm to the regular expression (a|b)*abb(a|b)* is the following:

NFA
b)*abb(a

Applying the determination algorithm to the above NFA, the following determination table is obtained:

Determination table
{

Graphically, the DFA is represented as follows:

DFA
b)*abb(a

The minimization tree is as follows:

Minimization tree

Given the minimization tree above, the final minimal DFA is as follows:

Minimal DFA
b)*abb(a

@@ Line 1: / Line 1: @@
 {{TOCright}}
-==Problem??
+==Problem ==
 Use Thompson's algorithm to build the NFA for the following regular expression. Build the corresponding DFA and minimize it.
@@ Line 212: / Line 212: @@
 {{CollapsedCode|Minimization tree|
-[[image:aula3p4mintree.jpg|200]]
+[[image:aula3p4mintree.jpg|350px]]
 }}
-The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).
+<!--The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for non-final states and the {0, 2} "a" and "b" transitions. The final states are all indistinguishable, regarding both "a" or "b" transitions (remember that, at this stage, we assume that individual states -- i.e., the final states -- are all indistinguishable).
+-->
 Given the minimization tree above, the final minimal DFA is as follows: