Zadanie 1

Zakładamy że każda prawa strona reguły gramatyki zaczyna się od nawiasu otwierającego a kończy się nawiasem zamykającym. Nawiasy nie występują w środku reguły. Ponadto zakładamy że dla różnych symboli pomocniczych prawe strony reguł są różne. Opisać słownie jak można przeprowadzić analizę syntaktyczną dla takiej gramatyki.

Zadanie 2

Zakładamy że dla każdego symbolu pomocniczego prawe strony reguł dla tego symbolu zaczynają się od różnych symboli końcowych. Np:


S : 'a' X
  | 'b' Y
  ;

X : 'c' Z Z
  | 'd' S
  ;

Y : 'a' ;

Z : 'a' Z Y
  | 'c' Y
  ;

Uzasadnić że gramatyka tego typu jest jednoznaczna.

Zadanie 3

Napisać gramatykę bezkontekstową opisującą listy składające się z pewnej liczby symboli 'x' oddzielonych średnikami. Dopuszczamy użycie kilku średników do oddzielenia dwu 'x'-ów i średnik na końcu. Np:

x;;x;x;

Zadanie 4

Napisać 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ą.

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