Lemat o pompowaniu dla języków bezkontekstowych

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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}[1].

Technika dowodzenia[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

Przypisy

  1. ftp.mimuw.edu.pl/People/urzy/Jaio/jaio0203.pdf