W
ykªad
4.
Determinist y zne
automat y
sk
o« zone
1.
(3p.)
P
o
da
j
determinist y zn
y
automat sk
o« zon
y
ak
eptuj¡ y
te
sªo
w
a
nad
alfab
etem
{0, 1}, w który h midzy ka»dymi dwoma kolejnymi jedynkami jest parzysta li zba
zer.
Jedno
z
mo»liwy h
rozwi¡za«
to:
0
1
0,1
0
1
1
0
2.
(3p.)
P
o
da
j
determinist y zn
y
automat sk
o« zon
y
ak
eptuj¡ y
te
sªo
w
a
nad
alfab
etem
{a, b}
ababb
,
które
za
wiera
j¡
p
o
dsªo
w
o
.
b
a
a
a,b a
b
a
b
b
a
b
3.
(4p.)
P
o
da
j
determinist y zn
y
automat sk
o« zon
y
ak
eptuj¡ y
prze i ie
jzyk
ó
w
ak
epto
w
an
y
h
przez
automat y:
a b
a b
→ F 1 2 2
→ 1 2 1
2 1 1
F
2 1 1
Oto
automat pro
dukto
wy
ak
eptuj¡ y
prze i ie
t
y
h
jzyk
ó
w:
(1,1)
(1,2)
a
b
a
a,b
→ (1, 1) (2, 2) (2, 1) b
b
F
(1, 2) (2, 1) (2, 1) a
(2, 1) (1, 2) (1, 1) a,b (2, 2) (1, 1) (1, 1) (2,1)
(2,2)
6