Przykładowy zestaw pytań na zaliczenie wykładu z PTA
Uwaga: W zadaniach zamkniętych (testowych) należy wybrać jedną odpowiedz
.
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)
Znalez
ć 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