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