Algoritmus
II:
Odstranění nedeterminismu
Myšlenka
: Anal
o
gie p
ředchozího algoritmu s
tím rozdílem, že budeme postupně přidávat
pouze stavy, které jsou dostupné
b
a
a
q
1
s
f
b
c
c
q
2
b
b
c
c
Ilustrace:
Q
DKA
=
{
{
s
}
}
a
{
s
}
Pro stav {
s
}:
Přidej nové stavy
{
q
1
,
f
}
,
{
q
2
,
f
}
do
Q
DKA
Pro stav
{
q
1
,
f
}
: …
...
Pro stav
{
q
2
,
f
}
: …
Přidej nové stavy
…
{
q
1
,
f
}
b
...
c
{
q
2
,
f
}
...
23
/44