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