Języki, automaty i obliczenia/Ćwiczenia 10: Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia 10

Ćwiczenie 1

Wykorzystując lemat o pompowaniu, udowodnij, że następujące języki nie są bezkontekstowe:

Rozwiązanie

Lemat 1 (Ogden)

Dla dowolnego języka bezkontekstowego istnieje liczba naturalna taka, że każde słowo , w którym wyróżniono lub więcej pozycji, można przedstawić w formie , gdzie oraz

  1. zawiera przynajmniej jedną wyróżnioną pozycję,
  2. zawiera co najwyżej wyróżnionych pozycji,
  3. dla

Lemat o pompowaniu jest szczególnym przypadkiem lematu Ogdena. Lemat Ogdena można próbować stosować w tych przypadkach, w których lemat o pompowaniu nie działa.

Ćwiczenie 2

Stosując lemat Ogdena pokaż, że język nie jest bezkontekstowy.

Rozwiązanie

Ćwiczenie 3

Udowodnij, że dla dowolnego języka nad alfabetem jednoelementowym

Rozwiązanie

Ćwiczenie 4

Udowodnij, że język jest bezkontekstowy.

Rozwiązanie

Ćwiczenie 5

Czy gramatyka poprawnych nawiasów
gdzie

jest jednoznaczna?

Rozwiązanie

Ćwiczenie 6

Określ gramatyki generujące języki:

  1. ,
  2. .

Czy gramatyki te są jednoznaczne?

Rozwiązanie

Ćwiczenie 7

Dana niech będzie gramatyka ( jest symbolem początkowym):

Używając algorytmu Cocke'a-Youngera-Kasamiego, sprawdź, czy poniższe słowa należą do języka generowanego przez tę gramatykę:

  1. ,
  2. ,
  3. .
Rozwiązanie
ZADANIA DOMOWE

Ćwiczenie 8

Wykorzystując lemat o pompowaniu, udowodnij, że następujące języki nie są bezkontekstowe:

Ćwiczenie 9

Stosując lemat Ogdena, pokaż, że język gdzie nie jest bezkontekstowy.

Wskazówka

Ćwiczenie 10

Udowodnij, że język jest bezkontekstowy.

Ćwiczenie 11

Czy gramatyka poprawnych nawiasów

gdzie

rozważana w przykładzie 1.2 jest jednoznaczna?

Ćwiczenie 12

Określ gramatyki generujące języki:

  1. ,
  2. .

Czy gramatyki te są jednoznaczne? Wykaż, że język jest jednoznaczny.

Ćwiczenie 13

Napisz algorytmy rozstrzygające, czy dany język bezkontekstowy jest:

  1. nieskończny,
  2. niepusty.

Ćwiczenie 14

Dana niech będzie gramatyka ( jest symbolem początkowym):

Używając algorytmu Cocke'a-Youngera-Kasamiego, sprawdź, czy poniższe słowa należą do języka generowanego przez tę gramatykę:

  1. ,
  2. ,
  3. .