Zadanie 1

Wyznaczyć język generowany przez poniższą gramatykę (z symolu początkowego S, jedynym symbolem końcowym jest 'x'):

S : A T | T ;
T : B U | U ;
U : C V | V ;
V : D W | W ;
W : E X | X ;
X : /* puste */ |  'x' ;
E : 'x' 'x' ;
D : E E ;
C : D D ;
B : C C ;
A : B B ;

Zadanie 2

Mamy następującą gramatykę:

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

Zadanie 3

Mamy następującą gramatykę:

S : 'a' | S 'a' | S T 'b' ;
T : 'c' | T 'x' 'c' ;

Uzasadnić że jest on jednoznaczna.

Zadanie 4

Napisać jednoznaczną gramatykę bezkontekstową opisującą listy odzielone średnikami których elementami są listy 'x' oddzielonych precinkami, np:

x,x;x,x,x;x,x

Uwaga: ten opis jest celowo nieprecyzyjny, proszę uzupełnić szczeguły według uznania i wyjaśnić jak się one tłumaczą na gramatykę.

Gramatykę bezkontekstową nazywamy regularną jeśli każda prawa strona reguły zawiera co najwyżej jeden symbol pomocniczy i ten symbol występuje na końcu, np:

S : 'x' S
  | 'y' 'z' 't' S
  | 'a'
  ;

Zadanie 5

Uzasadnić że język skończony (składający się ze skończenie wielu słów) można opisać gramatyką regularną, przy tym dodatkowo można żądać by prawe strony reguł albo składały się z pojedyńczego symbolu końcowego, albo z pojedyńczego symbolu końcowego po którym występuje symbol pomoczniczy.

Zadanie 6

Symbolami końcowymi jęzka są nawiasy '(', ')', '[', ']', '{', '}'. Napisać gramatykę dla układów poprawnie zagniżdżonych nawiasów (nawiasowi otwierającemu ma odpowiadać nawias zamykający tego samego rodzaju), np:

([]([][]))[]()

Zastanowić się czy da się podać gramatykę regularną dla tego języka (jeśli narzucimy górne orgraniczenie na głębokość zagnieżdżania to taka gramatyka istnieje).