Prawidłowe zastosowanie lematu pompowania CFL

Aug 16 2020

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

1 vonbrand Aug 17 2020 at 08:20

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ą.