Lemat o pompowaniu dla języków bezkontekstowych

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

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