Prawidłowe zastosowanie lematu pompowania CFL
Natknąłem się na to pytanie o pokazanie tego języka $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$jest bezkontekstowa, ale nie linearna w książce Petera Linza. Można to łatwo zrobić dzięki oddzielnemu lematowi o pompowaniu dla języków liniowych (jak podano w książce Linza), ale moje pytanie jest inne.
Najwyraźniej jest to CFL i można do tego skonstruować automat wpychający. Ale jeśli zastosuję lemat o pompowaniu do świetlówek kompaktowych, stwierdzam, że jestem w stanie pompować struny, które nie należą do tego języka, co oznaczałoby, że język nie jest CFL. Najwyraźniej robię coś złego.
Korzystając z formatu „podobnego do gry” podanego w Linzu, powiedz, że wybierasz $w = a^mb^mc^{2m}$, $|w| \ge m$. Przeciwnik może wybrać kilka rozkładów$w = uvxyz$, mogą wyglądać jak -:
- $v = a^k, y = a^l$: Przypadek, w którym $|vxy|$ jest zawarty w $a$jest ze sznurka. Pompa$i = 0$, i wtedy $w_0 = a^{m – (k + l)}b^mc^{2m}$ nie może być w języku, ponieważ równość już nie obowiązuje.
- $v = a^k, y = b^l$: Przypadek, w którym $v$ jest w $a$ Sekcja, $x$ obejmuje $a$jest i $b$'s i $y$ jest w $b$Sekcja. Ponownie pompuj$i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ nie może być w języku.
Takich przypadków jest więcej. Gdzie popełniam błąd w stosowaniu CFL PL?
Odpowiedzi
Lemat o pompowaniu dla CFL stwierdza, że jeśli $L$ jest CFL, istnieje stała $N \ge 1$ takie, że dla wszystkich $\omega \in L$ z $\lvert \omega \rvert \ge N$ istnieje podział $\sigma = u v w x y$ z $\lvert v w x \rvert \le N$ i $v x \ne \varepsilon$ takie że $u v^k w x^k y \in L$ dla wszystkich $k \ge 0$.
(Lemat o pompowaniu dla zwykłych języków jest podobny, poniższa dyskusja dotyczy z niewielkimi zmianami).
Chcesz to udowodnić przez zaprzeczenie $L$nie jest CFL. Więc zakładasz$L$jest CFL i jest zaprzeczeniem lematu. Oznacza to szczegółowo:
- Tak jak $L$jest CFL, spełnia lemat. W szczególności istnieje stała$N$ takie, że ...
- Jak stwierdza lemat, wszystkie długie struny są w$L$ można podzielić, możesz wybrać taki, z którym łatwo się pracuje.
- Lemat stwierdza, że istnieje pewien podział$\omega$takie, że .... dla wszystkich $k \ge 0$...; aby zaprzeczyć lematowi, musisz udowodnić, że żaden podział nie działa. W praktyce bierzesz określony podział swojego$\omega$( dowolny podział) i do tego wybierz trochę$k$za to, że nie podaje łańcucha w języku. Może być konieczne podzielenie tego na przypadki.
Co się dzieje z ciągami znaków, które nie należą do języka lub są krótsze niż $N$, jest całkowicie nieistotne. Może się zdarzyć, że niektóre struny można pompować, że niektóre wartości$k$praca dla wszystkich łańcuchów, ... Najważniejsze jest to, że dla jednego ciągu$\omega$(ten, który wybrałeś) żaden podział nie działa z jedną wartością$k$(znowu ten, który wybrałeś). Jak twierdzi lemat, działa to dla wszystkich wystarczająco długich łańcuchów, z pewnym podziałem dla wszystkich $k$wystarczy jeden kontrprzykład. Nieskończone przykłady niczego nie dowodzą.