Lemat o pompowaniu dla języków bezkontekstowych

Z Wikipedii

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.

Spis treści

1 Treść lematu
2 Dowód lematu
3 Technika dowodzenia
4 Literatura

[edytuj] Treść lematu

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

przynajmniej jedno z $v\,$ , $x\,$ jest niepuste
długość $vwx\,$ wynosi co najwyżej $n\,$
dla każdego $k\in N,$ , słowo postaci $uv^kwx^ky\,$ , w szczególności $uwy\,$ , należy do tego języka

[edytuj] 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 $G$ . Oznaczmy przez $p$ najmniejszą taką liczbę, że dla każdej produkcji $\alpha\Rightarrow\beta$ z gramatyki $G$ zachodzi $p\geq |\beta|$ . Przez $m$ oznaczmy ilość symboli nieterminalnych w gramatyce $G$ . Pokażemy teraz, że dla $n = p m + 1$ zachodzi teza twierdzenia.

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

Zauważmy więc, że iterując drugie przekształcenie $k$ razy możemy wygenerować używając gramatyki $G$ słowo $u v k w x k y$ . Niepustość słowa $v x$ 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ść $|vxy|\leq n$ wynika z tego, że wysokość poddrzewa zaczepionego w drugim od dołu nieterminalu jest nie większa od $m + 1$ - taki wybraliśmy, a rozgałęzienie drzewa co najwyżej $p$ , zatem długość słowa $v x y$ nie może być dłuższa niż $n = p m + 1$ . ^[1]

[edytuj] 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łą $n\,$ .
Budujemy słowo $z\,$ , być może zależne od $n\,$ .
Pokazujemy, że niezależnie od podziału słowa $z\,$ na $uvwxy\,$ dla pewnego $k\,$ słowo $uv^kwx^ky\,$ nie należy do badanego języka. W ten sposób otrzymujemy sprzeczność i kończymy dowód nie wprost.