Lemat o pompowaniu dla języków bezkontekstowych


Lemat o pompowaniu dla języków bezkontekstowych w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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

Treść lematu | edytuj kod

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

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

Dowód lematu | 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 . {\displaystyle G.} Oznaczmy przez p {\displaystyle p} najmniejszą taką liczbę, że dla każdej produkcji α β {\displaystyle \alpha \Rightarrow \beta } z gramatyki G {\displaystyle G} zachodzi p | β | . {\displaystyle p\geqslant |\beta |.} Przez m {\displaystyle m} oznaczmy ilość symboli nieterminalnych w gramatyce G . {\displaystyle G.} Pokażemy teraz, że dla n = p m + 1 {\displaystyle n=p^{m+1}} zachodzi teza twierdzenia.

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

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

Technika dowodzenia | 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 . {\displaystyle n.}
  • Budujemy słowo z , {\displaystyle z,} być może zależne od n . {\displaystyle n.}
  • Pokazujemy, że niezależnie od podziału słowa z {\displaystyle z} na u v w x y {\displaystyle uvwxy} dla pewnego k {\displaystyle k} słowo u v k w x k y {\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ż | edytuj kod

Przypisy | edytuj kod

  1. ftp://ftp.mimuw.edu.pl/People/urzy/Jaio/jaio0203.pdf.
Na podstawie artykułu: "Lemat o pompowaniu dla języków bezkontekstowych" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy