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

k

a»dymi

dw

oma

k

olejn

ymi

jedynk

ami

jest

parzysta

li zba

zer.

Jedno

z

mo»liwy

h

rozwi¡za«

to:

0

1

1

0

0

0,1

1

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}

,

które

za

wiera

j¡

p

o

dsªo

w

o

ababb

.

b

a

b

a

b

a

b

a

b

a

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

→ F 1 2 2

2 1 1

a b

→ 1 2 1

F

2 1 1

Oto

automat

pro

dukto

wy

ak

eptuj¡ y

prze i ie

t

y

h

jzyk

ó

w:

a

b

→ (1, 1) (2, 2) (2, 1)

F

(1, 2) (2, 1) (2, 1)
(2, 1) (1, 2) (1, 1)
(2, 2) (1, 1) (1, 1)

(2,1)

(2,2)

(1,1)

(1,2)

b

a

a,b

a

b

a,b

6