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 \mathbb{N}$ słowo postaci $u{v}^{k}w{x}^{k}y,$ 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⩾|\beta |.$ Przez $m$ oznaczmy liczbę 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 $m+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ż $m$ co najmniej jeden symbol nieterminalny powtarza się (i to wśród ostatnich $m+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 $u{v}^{k}w{x}^{k}y.$ 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ść $|vwx|⩽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 $u{v}^{k}w{x}^{k}y$ 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