ykªad 5.
Niedeterminist y zne
automat y
sk
o« zone
{a, b}
1.
(2
p.)
P
o
da
j
automat niedeterminist y zn
y
ak
eptuj¡ y
sªo
w
a
nad
alfab etem ababb za
wiera j¡ e
p
o
dsªo w
o
.
a,b a,b a b a b b 2.
(5
p.)
Zdeterminizuj nastpuj¡ y
automat niedeterminist y zn
y:
b a b a a a s p q b Oto
o
dp
o
wiedni automat p
otgo wy
(ograni zon
y
do
stanó w
osi¡
galn y
h):
a,b a
{s,p}
a
{s}
b
{s,p,q}
b b
{q}
ε
3.
(3
p.)
W
y
elimin uj
-przej± ia
w
p
oni»szym automa ie.
Jaki jzyk on
ak
eptuje?
a a ε
b, ε
b, ε
b, Oto
jedno z
mo»liwy h
rozwi¡za«.
Nie
jest ono
na
jprostsze, ale
jest wynikiem zasto-so
w
ania k
onstruk ji
przedsta wionej na
wykªadzie.
Jzyk ak
epto w
an
y
przez automat, a∗b?b?b?a∗
to
.
a a,b a a,b a,b b b b 7