W

ykªad

6.

Ró

wno

w

a»no±¢

wzor ó

w,

wyra»e«

regularn y

h

i

automató w

sk

o« zon

y

h

1.

(3

p.)

Dopasuj

do

siebie

automat

y

i

wyra»enia regularne: a(ba | b)∗

1)

,

b

- v a - v j

?

6

a

b(bb | a)∗

a)

2)

,

a

- v b - v j

?

a(aa | b)∗

6

3)

,

b

b)

a

?

b(ab | a)∗

- v b - vj

4)

.

6

a

)

b

- v a - v j

?

6

b

d)

Rozwi¡zanie: 1-d,

2-b,

3-a,

4-

b(aba | aa)+a 2.

(4

p.)

P

o

da

j

automat

sk

o« zon

y

ak

eptuj¡ y

jzyk

opisan

y

wzor em:

.

Oto

kilk

a

mo»liwy

h

rozwi¡za«: ε

b

a

a

b

a

a

a

a

b

a

a

b

a

a

a

a

a

b

b

a

a

a

a

8

3.

(3

p.)

P

o

da

j

wyra»enie regularne opisuj¡ e

jzyk

ak

epto

w

an

y

przez

nastpuj¡ y

automat

niedeterminist y zn

y:

a

b

→ F 1 2, 3 4

2

1

3

1

4

1

1

(ab | aa | b(a | b))∗ (ab | aa | ba | bb)∗

((a | b)(a | b))∗

,

lub

.

9