ykªad
12.
Automat
y
stoso
w
e
1.
(4
p.)
Sk
onstruuj automat
stoso
wy
ak
eptuj¡ y
wyra»enia na
wiaso
w
e
za
wiera
j¡ e
()[]{}
trzy
ro
dza
je
na
wiasó
w:
,
przy
zym:
(a)
na
wiasy
okr¡
gªe
mog¡
zna
jdo
w
a¢
si
w
ewn¡trz
na
wiasó
w
okr¡
gªy
h,
kw
adrato-
wy
h
lub
w
¡sat
y
h,
(b)
na
wiasy
kw
adrato
w
e
mog¡
zna
jdo
w
a¢
si
w
ewn¡trz
na
wiasó
w
kw
adrato
wy
h
lub
w
¡sat
y
h,
( )
na
wiasy
w
¡sate
mog¡
zna
jdo
w
a¢
si
t
ylk
o
w
ewn¡trz
na
wiasó
w
w
¡sat
y
h.
()[[()(())]][]
[[]]([][]) Na
przykªad, jest
p
opra
wn
ym
wyra»eniem na
wiaso
wym,
a
nie
jest.
K
onstruk
ja
automatu przyp
omina
k
onstruk
j
automatu stoso
w
ego
z
wykªadu
roz-
p
ozna
j¡ ego
wyra»enia na
wiaso
w
e
zbudo
w
ane
t
ylk
o
z
jednego
ro
dza
ju
na
wiasó
w.
Ma
s
on
jeden
stan
,
a
na
stosie
opró
z
pinezki
prze
ho
wyw
ane
s¡
na
wiasy
zam
yk
a
j¡ e,
który
h
sp
o
dziew
am
y
si
jesz ze
na
w
ej± iu.
(
(s, x) → (s, )x) x =⊥, }, ], ) dla
[
(s, x) → (s, ]x) x =⊥, }, ]
dla
{
(s, x) → (s, }x) x =⊥, }
dla
x
(s, x) → (s, ε) x =}, ], ) dla
ε
(s, ⊥) → (s, ε) 2.
(3
p.)
Przeksztaª¢
gramat
yk
:
S → aSa | bSb | a | b | ε
{a, b}
generuj¡ ¡
palindrom y
(nad
alfab
etem
),
na
automat
stoso
wy
(stosuj¡
k
on-
struk
j
p
o
dan¡
w
t
ym
wykªadzie).
S
Oto
rozwi¡zanie.
Aksjomat p
eªni
tu
rol
pinezki.
ε
(s, S) → (s, aSa) ε
(s, S) → (s, bSb) ε
(s, S) → (s, a) ε
(s, S) → (s, b) ε
(s, S) → (s, ε) a
(s, a) → (s, ε) b
(s, b) → (s, ε) ε
(s, ⊥) → (s, ε) 16
(3
p.)
Przeksztaª¢
automat
stoso
wy
ak
eptuj¡ y
wyra»enia na
wiaso
w
e:
[
(s, x) → (s, ]x) x =], ⊥
dla
]
(s, ]) → (s, ε) ε
(s, ⊥) → (s, ε) na
ró
wno
w
a»n¡
m
u
gramat
yk
b
ezk
on
teksto
w
¡
(stosuj¡
k
onstruk
j
p
o
dan¡
w
t
ym
wykªadzie).
⊥ ]
S
P
Sym
b
ole
stoso
w
e
i
reprezen tujem
y
,
o
dp
o
wiednio, za
p
omo
¡
nieterminali i
,
S
przy
zym
jest
aksjomatem.
S → [P S | ε
P
→ [P P | ]
17