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:

1)

a

(ba | b)

∗

,

2)

b

(bb | a)

∗

,

3)

a

(aa | b)

∗

,

4)

b

(ab | a)

∗

.

a)

-

v

-

vj







?





6

a

a

b

b)

-

v

-

vj







?





6

b

b

a

)

-

v

-

vj







?





6

b

a

a

d)

-

v

-

vj







?





6

a

b

b

Rozwi¡zanie:

1-d,

2-b,

3-a,

4-

2.

(4

p.)

P

o

da

j

automat

sk

o« zon

y

ak

eptuj¡ y

jzyk

opisan

y

wzor em:

b

(aba | aa)

+

a

.

Oto

kilk

a

mo»liwy

h

rozwi¡za«:

b

a

a

a

b

a

a

ε

b

a

a

a

b

a

a

a

a

b

a

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)

∗

lub

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

∗

.

9