Zadanie 1

Automat z stosem ma taśmę wejściową na której w danym momencie widzi jeden znak i po której przesuwa się tylko do przodu. Ma też stos na którym zapamiętuje stany i symbole. W danym momencie automat może wykonać jedną z trzech rodzajów operacji, mianowicie przesuniecie, redukcję lub stop. Przesunięcie zapamiętuje bieżący stan i bieżący symbol na stosie i przesuwa się do przodu po taśmie wejsciowej. Redukcje są związane z regułami gramatyki: logicznie redukcja zastępuje prawą stronę reguły przez lewą, tzn. jesli prawa stron redukcji ma długość k to odczytuje się ze stosu k par symboli i stanów. Ostatni odczytany stan staje się bieżącym stanem. Następnie automat przechodzi do nowego stanu na zależnie od bieżącego stanu (przed chwilą odczytanego ze stosu) i symbolu z lewej strony produkcji. Jeśli operacją jest stop to automat zatrzymuje się albo akceptując albo zgłaszając błąd. Poniższy pseudo kod ilustruje dzialanie automatu:

stan = poczatkowy;
while (1) {
   znak = daj_znak();
   switch(akcja(stan, znak)) {
       case przesuniecie:
            push(stan, znak);
            stan = przejscie(stan, znak);
	    znak = daj_znak();
	    break;
       redukcja_1:
            for(i=0; i < dlugosc1; i++) {
	        (stan, _) = pop();
            }
            push(stan, nonterminal1);
            stan = przejscie(stan, nonterminal1);
	    break;
        redukcja_2:
	    ...
	stop_błąd:
	    ...
	stop_akceptuj:
    }
}

W0 : W EOF ;
W : T | W '+' T ;
T : 'x' | '(' W ')' ;

Zadanie 2

• 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ą

Zadanie 3

Zadanie 4