Zadanie 1

Automat skończony jest zadany następującą tabelą przejścia:

stan 0: 'e' -> 1; [a-df-z] -> 4
stan 1: 'n' -> 2; [a-mo-z] -> 4; '_' -> 5
stan 2: 'd' -> 3; [a-ce-z] -> 4; '_' -> 5
stan 3: [a-z] -> 4; '_' -> 5
stan 4: [a-z] -> 4; '_' -> 5
stan 5: [a-z] -> 4

gdzie dla każdego stanu po dwukropku podajemy dozwolone przejścia, przy tym po strzałce jest numer stanu do którego mamy przejść. Stanem początkowym jest stan 0. W stanie 3 akceptujemy z wynikiem pierwszym. W stanie 4 akceptujemy z wynikiem drugim. Sprawdzić jak nasz automat zachowa się na następujących ciągach: "end", "end_", "_ala", "a__la", "a_l_a", "endala", "end_ala". Jak można zinterpretować wyniki tego automatu. Pokazać że ten automat jest minimalny. Pokazać że jeśli potraktujemy oba wyniki jako równoważne (tzn. przyjmiemy stany 3 i 4 po prostu jako akceptujące) to automat nie będzie minimalny. Znaleźć minimalną wersję po tej modyfikacji.

Zadanie 2

W pewnym języku programowania część znacząca liczby zmiennopozycyjnej to ciąg cyfr, znaków podkreślenia i kropki. Dokładniej, ten ciąg ma zawierać dokładnie jedną kropkę i co najmniej jedną cyfrę. Znaki podkreślenia można używać dla poprawy czytelności. Przed częścią znaczącą może (ale nie musi) wystąpić znak (tzn. '+' lub '-'). Po części znaczącej może wystąpić litera 'd' lub 'e'. Jeśli taka litera wystąpi to po literze musi wystąpić wykładnik tzn. liczba całkowita. Na początku wykładnika może (ale nie musi) wystąpić znak (tzn. '+' lub '-'). W wykładniku również można umieszczać znaki podkreślenia. Napisać wyrażenie regularne opisujące te liczby. Następnie napisać odpowiednią gramatykę bezkontekstową.

Zadanie 3

W pewnym języku programowania identyfikatory zaczynają się od litery lub znaku podkreślenia. Następne znaki indentyfikatora to litery, znak podkreślenia lub czyfry, dodatkowo, jeśli w indentyfikatorze wystąpił znak podkreślenia w częśli po nim dopuszczamy '+', '-', '=', '<', '>'. Napisać wyrażenie regularne opisujące takie identyfikatory.

Zadanie 4

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)
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.

Zadanie 5

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.