Zadanie 1

Zakładamy że gramatyka z wykładu została rozszerzona o dodatkowe reguły w podobnym stylu i że operatory umieszczamy w węźle drzewa rozbioru odpowiadającym regule (a nie w węźle potomnym). Narysować struktury drzewiaste dla wyrażeń języka C: 'x * y - w - z', 'x * (y - w - z)', 'x * y - (w - z)', '*x * *y - w - z', 'x ? y : z + w', 'x * (y += z - w)'.

Zadanie 2

W językach programowania występują struktury o stopniu rozgałęzienia większym niż dwa (w C instrukcje 'for' i 'while' czy wywołanie funkcji). Jak można reprezentować struktury o większym stopniu rozgałęzienia przy pomocy struktur o stopniu rozgałęzienia dwa (dlaczego stopień rozgałęzienia 1 to za mało). Zastanowić się jakie są wady a jakie zalety struktur o stopniu rozgałęzienia dwa w porównaniu do bezpośredniego użycia struktur o większym stopniu rozgałęzienia.

Zadanie 3

Wyobraźmy sobie że mamy w tablicy (buforze) tekst (linię). Interesuje nas czy linia spełnia jeden z poniższych warunków:

czwarty znak to 'A'
jedenasty znak od końca to 'A'
w tekscie występuje 'A' a dalej 'B', tak że pomiędzy 'A' i 'B' nie ma 'C' (ale mogą być inne znaki).
w tekscie po słowie 'Ala' wystepuje słowo 'Ola' (być może oddzielone innymi słowami)
w tekście są poprawnie sparowane nawiasy
tekst ma długość podzielną przez trzy
tekst ma długość będącą liczbą pierwszą
tekst jest liczbą podzielną przez trzy
tekst jest liczbą pierwszą

Które z tych warunków może sprawdzić automat skończony. Kiedy i jak automat pomaga w rozwiązaniu.