Odstranění nedeterminismu
Myšlenka:
Vytvořit stavy ze všech podmnožin
množiny stavů KA bez
e
-přechodů a přidat
přechody mezi nimi tak, aby simulovaly
přechody původního automatu.
q
1
s
b
f
b
c
c
a
q
2
a
b
b
c
c
Ilustrace:
Q
DKA
=
{
{
s
}, {
q
1
}, {
q
2
}, {
f
}, {
s
,
q
1
},
{
s
,
q
2
}, {
s
,
f
}, {
q
1
,
q
2
}, {
q
1
,
f
}, {
q
2
,
f
},
{
s
,
q
1
,
q
2
}, {
s
,
q
1
,
f
}, {
s
,
q
2
,
f
}, {
q
1
,
q
2
,
f
},
{
s
,
q
1
,
q
2
,
f
}
}
a
c
{
q
2
,
f
}
...
{
q
1
,
f
}
b
...
Pro
sta
v
{
s
,
f
}:
{
s
,
f
}
Pro
sta
v
{
s
}:
…
...
...
Pro
sta
v
{
s
,
q
1
,
q
2
,
f
}:
…
1
4
/44