Lemat o pompowaniu dla języków bezkontekstowych

Lemat o pompowaniu dla języków bezkontekstowych to twierdzenie służące do udowadniania, że dany język nie jest bezkontekstowy. Jego uogólnieniem jest lemat Ogdena.

Treść lematu edytuj

Dla każdego języka bezkontekstowego istnieje taka stała   że dla każdego słowa   należącego do tego języka o długości co najmniej   możemy podzielić to słowo na   w taki sposób, że:

  • przynajmniej jedno z     jest niepuste
  • długość   wynosi co najwyżej  
  • dla każdego   słowo postaci   w szczególności   należy do tego języka

Dowód lematu edytuj

Przypomnijmy, że dla każdego języka bezkontekstowego istnieje gramatyka bezkontekstowa, która go generuje. Dla rozpatrywanego języka oznaczmy tę gramatykę przez   Oznaczmy przez   najmniejszą taką liczbę, że dla każdej produkcji   z gramatyki   zachodzi   Przez   oznaczmy liczbę symboli nieterminalnych w gramatyce   Pokażemy teraz, że dla   zachodzi teza twierdzenia.

Przyjrzyjmy się minimalnemu drzewu wyprowadzenia słowa   w gramatyce   (o najmniejszej liczbie wierzchołków). Ponieważ rozgałęzienie wynosi maksymalnie   to wysokość drzewa wynosi przynajmniej   Zauważmy więc, że na ścieżce prowadzącej od korzenia do dowolnego węzła o głębokości większej niż   co najmniej jeden symbol nieterminalny powtarza się (i to wśród ostatnich   wierzchołków), oznaczmy go przez   Zauważmy, że wywód słowa   możemy przedstawić jako złożenie przekształceń   następnie   a na końcu  

Zauważmy więc, że iterując drugie przekształcenie   razy możemy wygenerować używając gramatyki   słowo   Niepustość słowa   wynika z tego, że w przeciwnym wypadku można by pominąć drugi duży krok (z trzech) i uzyskać niższe drzewo wyprowadzenia, a przecież rozpatrywane tu jest minimalne. Nierówność   wynika z tego, że wysokość poddrzewa zaczepionego w drugim od dołu nieterminalu jest nie większa od   – taki wybraliśmy, a rozgałęzienie drzewa co najwyżej   zatem długość słowa   nie może być dłuższa niż  [1].

Technika dowodzenia edytuj

Lemat o pompowaniu wykorzystuje się, podobnie jak w przypadku języków regularnych, do dowodzenia nie wprost, że jakiś język nie jest bezkontekstowy. Plan dowodu jest następujący:

  • Zakładamy nie wprost, że język jest bezkontekstowy.
  • Z lematu o pompowaniu bierzemy stałą  
  • Budujemy słowo   być może zależne od  
  • Pokazujemy, że niezależnie od podziału słowa   na   dla pewnego   słowo   nie należy do badanego języka. W ten sposób otrzymujemy sprzeczność i kończymy dowód nie wprost.

Zobacz też edytuj

Przypisy edytuj