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 ${\displaystyle n,}$ że dla każdego słowa ${\displaystyle z}$ należącego do tego języka o długości co najmniej ${\displaystyle n,}$ możemy podzielić to słowo na ${\displaystyle uvwxy}$ w taki sposób, że:

• przynajmniej jedno z ${\displaystyle v,}$ ${\displaystyle x}$ jest niepuste
• długość ${\displaystyle vwx}$ wynosi co najwyżej ${\displaystyle n}$
• dla każdego ${\displaystyle k\in \mathbb {N} }$ słowo postaci ${\displaystyle uv^{k}wx^{k}y,}$ w szczególności ${\displaystyle 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 ${\displaystyle G.}$ Oznaczmy przez ${\displaystyle p}$ najmniejszą taką liczbę, że dla każdej produkcji ${\displaystyle \alpha \Rightarrow \beta }$ z gramatyki ${\displaystyle G}$ zachodzi ${\displaystyle p\geqslant |\beta |.}$ Przez ${\displaystyle m}$ oznaczmy liczbę symboli nieterminalnych w gramatyce ${\displaystyle G.}$ Pokażemy teraz, że dla ${\displaystyle n=p^{m+1}}$ zachodzi teza twierdzenia.

Przyjrzyjmy się minimalnemu drzewu wyprowadzenia słowa ${\displaystyle z}$ w gramatyce ${\displaystyle G}$ (o najmniejszej liczbie wierzchołków). Ponieważ rozgałęzienie wynosi maksymalnie ${\displaystyle p,}$ to wysokość drzewa wynosi przynajmniej ${\displaystyle 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ż ${\displaystyle m}$ co najmniej jeden symbol nieterminalny powtarza się (i to wśród ostatnich ${\displaystyle m+1}$ wierzchołków), oznaczmy go przez ${\displaystyle \gamma .}$ Zauważmy, że wywód słowa ${\displaystyle z}$ możemy przedstawić jako złożenie przekształceń ${\displaystyle \xi _{0}\Rightarrow u\gamma y,}$ następnie ${\displaystyle \gamma \Rightarrow v\gamma x,}$ a na końcu ${\displaystyle \gamma \Rightarrow w.}$

Zauważmy więc, że iterując drugie przekształcenie ${\displaystyle k}$ razy możemy wygenerować używając gramatyki ${\displaystyle G}$ słowo ${\displaystyle uv^{k}wx^{k}y.}$ Niepustość słowa ${\displaystyle 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ść ${\displaystyle |vwx|\leqslant n}$ wynika z tego, że wysokość poddrzewa zaczepionego w drugim od dołu nieterminalu jest nie większa od ${\displaystyle m+1}$ – taki wybraliśmy, a rozgałęzienie drzewa co najwyżej ${\displaystyle p,}$ zatem długość słowa ${\displaystyle vxy}$ nie może być dłuższa niż ${\displaystyle n=p^{m+1}}$^[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łą ${\displaystyle n.}$
• Budujemy słowo ${\displaystyle z,}$ być może zależne od ${\displaystyle n.}$
• Pokazujemy, że niezależnie od podziału słowa ${\displaystyle z}$ na ${\displaystyle uvwxy}$ dla pewnego ${\displaystyle k}$ słowo ${\displaystyle uv^{k}wx^{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

Przypisy