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
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
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
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ż
Przypisy
- ↑ ftp://ftp.mimuw.edu.pl/People/urzy/Jaio/jaio0203.pdf.