W

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

on

jeden

stan

s

,

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)

dla

x

=⊥, }, ], )

(s, x)

[

→ (s, ]x)

dla

x

=⊥, }, ]

(s, x)

{

→ (s, }x)

dla

x

=⊥, }

(s, x)

x

→ (s, ε)

dla

x

=}, ], )

(s, ⊥)

ε

→ (s, ε)

2.

(3

p.)

Przeksztaª¢

gramat

yk

:

S

→ aSa | bSb | a | b | ε

generuj¡ ¡

palindrom

y

(nad

alfab

etem

{a, b}

),

na

automat

stoso

wy

(stosuj¡

k

on-

struk

j

p

o

dan¡

w

t

ym

wykªadzie).

Oto

rozwi¡zanie.

Aksjomat

S

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, ε)

(s, a)

a

→ (s, ε)

(s, b)

b

→ (s, ε)

(s, ⊥)

ε

→ (s, ε)

16

3.

(3

p.)

Przeksztaª¢

automat

stoso

wy

ak

eptuj¡ y

wyra»enia

na

wiaso

w

e:

(s, x)

[

→ (s, ]x)

dla

x

=], ⊥

(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).

Sym

b

ole

stoso

w

e

⊥

i

]

reprezen

tujem

y

,

o

dp

o

wiednio,

za

p

omo

¡

nieterminali

S

i

P

,

przy

zym

S

jest

aksjomatem.

S

→ [P S | ε

P

→ [P P | ]

17