aboutsummaryrefslogtreecommitdiff
path: root/NDFA2DFAexample
blob: 53b8e77286064e101d7197cd74b8d2b37ff129f9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
This example from http://en.wikipedia.org/wiki/Powerset_construction

Comment: In the NDFA Extension to the VFSM syntax (VFSMv2N), lambda: and epsilon: are equivalent
Comment: In VFSMv2N, lambda: and epsilon: are special transitions indicating transition on no input
Start: 1
Accept: 3 4
Edges:
	1 0 2
	1 lambda: 3
	2 1 2
	2 1 4
	3 epsilon: 2
	3 0 4
	4 0 3
End:

Should become a DFA under powerset construction or equivalent

Start: {123}
Accept: {123} {24} {23} {4}
Edges:
	{123} 0 {24}
	{123} 1 {24}
	{24} 0 {23}
	{24} 1 {24}
	{23} 0 {4}
	{23} 1 {24}
	{4} 0 {23}
	{4} 1 {}
	{} 0 {}
	{} 1 {}
End: