Przykładowy zestaw pyta

ń

na zaliczenie wykładu z PTA

Uwaga: W zadaniach zamkni

ę

tych (testowych) nale

ż

y wybra

ć

jedn

ą

odpowied

ź

.

1. (2 pkt)
Narysowa

ń

diagram przej

ść

automatu DAS, który akceptuje wszystkie słowa ko

ń

cz

ą

ce si

ę

podsłowem

0110,

Σ

= {0,1}.

2. (1 pkt)
Konwersja, w której zmienia si

ę

mi

ę

dzy innymi zbiór stanów automatu, to:

A) NAS z

ε

-ruchami w NAS

B) NAS w DAS
C) Mealy’ego w Moore’a
D)

ż

adna z powy

ż

szych

3. (1 pkt)
Do którego wyra

ż

enia regularnego zostanie dopasowane słowo automat:

A) autt*mat
B) automatt+
C) auto(m|at)
D) automa[bsd.]

4. (2 pkt)
Skonstruowa

ć

automat NAS z

ε

-ruchami rozpoznaj

ą

cy j

ę

zyk opisany przez nast

ę

puj

ą

ce wyra

ż

enie

regularne: ab(abb)*

∪

aa*,

Σ

= {a,b}.

5. (2 pkt)
Znale

źć

wyra

ż

enie regularne, które opisuje j

ę

zyk akceptowany przez poni

ż

szy DAS. Przedstawi

ć

sposób otrzymania tego wyra

ż

enia regularnego

6. (2 pkt)
Wykaza

ć

,

ż

e podana gramatyka G jest niejednoznaczna.

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

S

→

AB

A

→

a|ab

B

→

bc|c

7. (1 pkt)
Wybierz zdanie prawdziwe z ni

ż

ej podanych.

A) Ka

ż

dy j

ę

zyk bezkontekstowy jest j

ę

zykiem regularnym.

B) Ka

ż

dy j

ę

zyk regularny jest j

ę

zykiem bezkontekstowym.

C) Ka

ż

dy j

ę

zyk bezkontekstowy jest akceptowany przez pewien automat NAS z

ε

-ruchami.

D) Ka

ż

dy j

ę

zyk bezkontekstowy jest akceptowany przez pewien deterministyczny automat ze

stosem (DAZS).

Punktacja:
5-6 pkt – dst

7 pkt – dst+

8-9 pkt – db

10 pkt – db+

11 pkt – bdb