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

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\geqslant |\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 $\gamma$. 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 $uv^kwx^ky$. Niepustość słowa $vx$ 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|\leqslant 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 $vxy$ nie może być dłuższa niż $n=p^{m+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łą $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.

Zobacz też

• Lemat o pompowaniu dla języków regularnych