Przykładowy zestaw zada

ń

na kolokwium z PTA

1. Skonstruowa

ć

DAS akceptuj

ą

cy wszystkie słowa nad alfabetem {a, b}

a) nie zawieraj

ą

ce jako podsłowa baa;

b) z nieparzyst

ą

liczb

ą

symboli a i nieparzyst

ą

liczb

ą

symboli b.

2. Zdeterminizowa

ć

nast

ę

puj

ą

cy automat niedeterministyczny:

3. 1) Zbudowa

ć

automat Mealy’ego, do wej

ś

cia którego wrzucane s

ą

monety o nominałach

1 zł, 2 zł i 5 zł. Automat wydaje sygnał „P”(parzysty), je

ś

li suma warto

ś

ci monet

jest parzysta, oraz „N”(nieparzysty), je

ś

li suma warto

ś

ci jest nieparzysta.

2) Konwertowa

ć

automat Mealy’ego na ekwiwalentny z nim automat Moore’a.

4. Przekształci

ć

NAS

ε

−

w NAS bez

ε

-przej

ść

a nast

ę

pnie w DAS:

5.Skonstruowa

ć

NAS

−

ε

dla wyra

ż

enia regularnego:

*

*

*

)

0

1

)

1

0

((

0

∪

=

R

.

6. Znale

źć

wyra

ż

enie regularne, które opisuje j

ę

zyk akceptowany przez automat:

q

2

q

1

a

b

a

b

q

3

a

b

7. Okre

ś

li

ć

j

ę

zyk jest generowany przez nast

ę

puj

ą

c

ą

gramatyk

ę

:

G=({A, B, S}, {a, b}, P, S)
P:

bb

Bbb

B

aa

Aaa

A

aabb

SAB

S

|

|

|

→

→

→

8. Wygenerowa

ć

słowo

)

(

ca

b

a

w

+

∗

=

dla podanej poni

ż

ej gramatyki i narysowa

ć

drzewo wywodu

:

G=({S}, {+,

∗

, a, b, c}, P, S)

P:

c

b

a

S

S

S

S

SS

S

S

|

|

|

|

|

|

)

(

+

∗

→

.