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