Lemat o pompowaniu dla języków bezkontekstowych

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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 | edytuj kod]

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 | edytuj kod]

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 ilość 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 | edytuj kod]

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 | edytuj kod]

Przypisy[edytuj | edytuj kod]