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 której może wystąpić litera 'd' lub 'e'. Po literze może 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ą.
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] -> 4gdzie 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.
S : S S | 'x'Jak wygląda język generowany przez tą gramatykę. Pokazać że gramatyka ta nie jest jednoznaczna zaś ilość drzew rozbioru rośnie wykładniczo z długością słowa (dokładnie jest to liczba Catalana: ((2*n-2)!)/(((n-1)!*(n-1)!)*n) ).