Theoretical Aspects of Lexical Analysis/Exercise 1

Problem

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

• (a|b)*

Solution

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

NFA for (a|b)*
{{{2}}}

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

In	α∈Σ	move(In, α)	ε-closure(move(In, α))	In+1 = ε-closure(move(In, α))
-	-	0	0, 1, 2, 4, 7	0
0	a	3	1, 2, 3, 4, 6, 7	1
0	b	5	1, 2, 4, 5, 6, 7	2
1	a	3	1, 2, 3, 4, 6, 7	1
1	b	5	1, 2, 4, 5, 6, 7	2
2	a	3	1, 2, 3, 4, 6, 7	1
2	b	5	1, 2, 4, 5, 6, 7	2

Graphically, the DFA is represented as follows: <dot-hack> digraph dfa { { node [shape=circle style=invis] start } rankdir=LR; ratio=0.5 node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 1 2 node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; start -> 0 0 -> 1 [label="a"] 0 -> 2 [label="b"] 1 -> 1 [label="a"] 1 -> 2 [label="b"] 2 -> 1 [label="a"] 2 -> 2 [label="b"] fontsize=10 } </dot-hack> Given the minimization tree to the right, the final minimal DFA is: <dot-hack> digraph dfamin { { node [shape=circle style=invis] start } rankdir=LR; ratio=0.5 node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 012 node [shape=circle,fixedsize=true,width=0.2,fontsize=10]; start -> 012 012 -> 012 [label="a"] 012 -> 012 [label="b"] fontsize=10 /*label="DFA for (a|b)*"*/ } </dot-hack>

The minimization tree is as follows. As can be seen, the states are indistinguishable. <dot-hack> digraph mintree { node [shape=none,fixedsize=true,width=0.2,fontsize=10] " {0, 1, 2}" -> "{}" [label="NF",fontsize=10] " {0, 1, 2}" -> "{0, 1, 2}" [label="F",fontsize=10] "{0, 1, 2}" -> "{0, 1, 2} " [label="a,b",fontsize=10] fontsize=10 /*label="Minimization tree"*/ } </dot-hack>