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: R = 0*((0 *"1)1*0)* .
6. Znalez
ć wyrażenie regularne, które opisuje język akceptowany przez automat:
b
a
q1 a q2
b
b
q3
a
7. Określić język jest generowany przez następującą gramatykę:
G=({A, B, S}, {a, b}, P, S)
P:
S SAB | aabb
A Aaa | aa
B Bbb | bb
8. Wygenerować słowo w = a "(b + ca) dla podanej poniżej gramatyki i narysować drzewo wywodu:
G=({S}, {+, ", a, b, c}, P, S)
P:
S (S) | SS | S "S | S + S | a | b | c .