Języki, automaty i obliczenia/Ćwiczenia 2: Gramatyka jako model obliczen. Hierarchia Chomsky'ego

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia 2

Ćwiczenie 1

Niech będzie systemem przepisującym. Sprawdź, czy w systemie tym można przepisać bezpośrednio słowo na słowo , jeśli , .

Rozwiązanie

Ćwiczenie 2

Zdefiniujmy zbiory: oraz

Udowodnij, nie obliczając w sposób bezpośredni, że w systemie przepisującym nie da się przepisać pośrednio słowa na słowo .

Rozwiązanie

Ćwiczenie 3

Niech . Rozważmy system przepisujący i określmy na zbiorze wszystkich -elementowych słów nad alfabetem binarną relację w następujący sposób:

(1) Pokaż, że jest relacją równoważności
(2) Udowodnij, że ind (to znaczy, że relacja ma klas abstrakcji)
Rozwiązanie punktu 1
Wskazaówka do punktu 2
Rozwiązanie punktu 2

Ćwiczenie 4

Określ języki generowane przez system przepisujący oraz zbiór , jeśli:

(1) , , ,
(2) , , ,
(3) , , .
Rozwiązanie do punktu 1
Rozwiązanie do punktu 2
Rozwiązanie do punktu 3

Ćwiczenie 5

Określ języki rozpoznawane przez system przepisujący oraz zbiór , jeśli:

(1) , , ,
(2) , , .
Rozwiązanie punktu 1
Rozwiązanie punktu 2

Ćwiczenie 6

Jaki język generuje gramatyka , jeśli:

(1) , ,
    ,
(2) , ,
    ,
Rozwiązanie punktu 1
Rozwiązanie punktu 2

Ćwiczenie 7

Podaj gramatykę która generuje język:

(1) ,
(2) ,
(3) ,
(4) ,
(5) .

Podajemy przykładowe gramatyki.

Rozwiązanie punktu 1
Rozwiązanie punktu 2
Rozwiązanie punktu 3
Rozwiązanie punktu 4
Rozwiązanie punktu 5

Ćwiczenie 8

Podaj gramatykę, która generuje język poprawnych wyrażeń arytmetycznych zbudowanych z operatorów dodawania i mnożenia oraz jednego argumentu oznaczonego symbolem . Przykładem takiego wyrażenia może być np. .

Rozwiązanie
ZADANIA DOMOWE

Ćwiczenie 9

Niech będzie systemem przepisującym. Sprawdź, czy w systemie tym można przepisać bezpośrednio słowo na słowo , jeśli:

(1) , ,
(2) , .

Ćwiczenie 10

Określ język generowany przez system przepisujący oraz zbiór , jeśli , , .

Ćwiczenie 11

Jaki język generuje gramatyka , jeśli:

(1) , ,
     ,
     ,
(2) , ,
     

Ćwiczenie 12

Podaj gramatykę, która generuje język:

(1) ,
(2) ,
(3) ,
(4) .

Ćwiczenie 13

Określ, do jakich klas (możliwie najwęższych) należą gramatyki, które generują języki z zadań 1.7 oraz 1.12.

Ćwiczenie 14

Załóżmy, że poprawny adres e-mailowy składa się z następujących elementów: niepustego identyfikatora złożonego z samych liter maksymalnie z czterech), znaku "małpy", niepustej nazwy serwera złożonej z samych liter (maksymalnie czterech), kropki oraz dwuliterowej nazwy domeny. Załóżmy, że alfabet składa się tylko z liter , i . Poprawnym adresem e-mailowym jest np. adres babc@aaa.cc. Zbuduj gramatykę, która generuje wszystkie poprawne adresy e-mailowe.