Jak mogę udowodnić, że ten język nie jest pozbawiony kontekstu?

Mam następujący język

$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$

Próbuję ustalić, do której klasy języka Chomsky pasuje. Widzę, jak można to zrobić za pomocą gramatyki kontekstowej, więc wiem, że jest przynajmniej wrażliwa na kontekst. Wydaje się, że nie byłoby możliwe stworzenie gramatyki bezkontekstowej, ale mam problem z udowodnieniem tego.

Wydaje się, że przekazuje pompowania widelca, ponieważ jeśli jest umieszczone w trzeciej części dowolnego słowa (sekcja z wszystkimi s). Może pompować i tyle razy, ile chcesz i pozostanie w języku. Jeśli się mylę, czy mógłbyś mi powiedzieć, dlaczego, jeśli mam rację, nadal uważam, że ten język nie jest pozbawiony kontekstu, więc jak mogę to udowodnić? $uvwxy$ $2$ $v$ $x$

formal-languages context-free formal-grammars pumping-lemma justausr
źródło

Nie jestem pewien, jak zrobić z tego formalny dowód, ale upewnienie się, że i <= j <= k wymaga kontekstu (wartość poprzedniej zmiennej).

Kevin

możliwy duplikat Jak udowodnić, że język nie jest pozbawiony kontekstu?

Raphael

@ Rafael, przeczytałem ten post przed tym i nie wiedziałem, jak zastosować go do mojego przykładu z powodu jego abstrakcyjności. Ponieważ stosunek każdego znaku jest> = liczba poprzednich znaków, nie mogłem zobaczyć, jak podzielić uxyzv na słowo, aby użyć lematu Ogdena. BlueMagister i jmad rozwinęli się w drugim poście, aby wyjaśnić to w moim przykładzie.

justausr

@Raphael Nie zgadzam się, że jest to trywialne zastosowanie ogólnej sprawy. Wybór, której metody użyć i jaki przykład zastosować, nie jest taki łatwy.

Gilles „SO- przestań być zły”

Odpowiedzi:

Możesz wymusić pompowanie w niektórych miejscach, używając lematu Ogdena , na przykład zaznaczając wszystkie zera.

Załóżmy, że jest pozbawiony kontekstu, wtedy lemat Ogdena daje ci , dajesz mu który jest w języku, i „zaznaczasz” wszystkie zera. Następnie każdy faktoryzacji musi być taka, że istnieje w lub . Możesz także założyć oraz ponieważ i muszą być podłańcuchami twojego języka. $p>0$ $w=0^p1^p2^p$ $w=uxyzv$ $0$ $x$ $z$ $x=a^k$ $z=b^m$ $xx$ $zz$

Jeśli to ma więcej niż 1 $z=0...0$ $w=ux^2yz^2v$
Jeśli i to ma więcej 1 niż 2. $x=0..0$ $z=1..1$ $w=ux^2yz^2v$
Jeśli i to ma więcej niż 1. $x=0..0$ $z=2..2$ $w=ux^2yz^2v$

Więc nie jest słowem w twoim języku. Dlatego nie jest pozbawiony kontekstu. $ux^2yz^2v$

Inne techniki można znaleźć w dyskusji: Jak udowodnić, że język nie jest pozbawiony kontekstu?

jmad
źródło

Czy to dla tego samego języka, który mam? Wydaje się, że dotyczy podobnego języka, w którym wszystkie zera 1 i 2 mają jednakową długość. Ten język ma liczbę 2> = liczbę 1> = liczbę 0

justausr

Tak, ale używając któregoś z pompujących lematów, możesz wybrać słowo (a ja wybrałem ): lemat Ogdena powinien działać na wszystkie z nich.

0^{p} 1^{p} 2^{p}

$0^p1^p2^p$

jmad

Gotcha, nigdy nie słyszałem o lemacie ogdena, więc będę musiał się temu przyjrzeć. Czy miałem rację stwierdzając, że zawodzi lemma pompowania?

justausr

@ justausr ja też nie, do niedawna (i dzięki dyskusji, o której wspomniałem). I tak, miałeś rację: lemat pompowania robi prawie to samo, ale brak wyboru miejsca do pompowania czyni go bezużytecznym.

jmad

Lemat pompujący powinien rozwiązać twój problem dotyczący trzeciej części słowa; zwróć uwagę, że kiedy dzielisz , każda kombinacja jest również w języku, w tym gdy . Spróbuj tego. $z = uvwxy$ $uv^nwx^ny$ $n = 0$

EDYCJA: Jak stwierdza jmad , Pumping Lemma jest jak gra:

Lemat pompowania daje $p$

Dajesz słowo języka o długości co najmniej $s$ $p$

Lemat pompujący przepisuje to w następujący sposób: z pewnymi warunkami ( i ) $s=uvxyz$ $|vxy|≤p$ $|vy|≥1$

liczbę całkowitą $n≥0$

Jeśli nie jest w , wygrywasz, nie jest pozbawiony kontekstu. $uv^nxy^nz$ $L$ $L$

Musisz więc podać słowo, podzielić 3 na przypadki i pokazać, że dla każdego przypadku można znaleźć , że wynikowe słowo nie jest w języku. $n$

Kiedy podzielisz , pomyśl o wszystkich przypadkach, w które może wpaść . Zauważ, że jeśli nie mieści się w 2, łatwo jest pompować 0 i 1, dopóki nie przewyższą 2, a wtedy masz słowo, które nie jest w języku. Moja sugestia jest taka, że jeśli wpada na 2 terytorium, możesz również sprawić, że i znikną ustawiając , więc . Następnie, eliminując 2, możesz dojść do słowa, które nie mieści się w języku. $s=uvxyz$ $vxy$ $vxy$ $vxy$ $v$ $y$ $n=0$ $uv^nxy^nz = uxz$

Blue Magister
źródło

Mówisz, że umieść wszystkie uvwxy w sekcji z 2?

justausr

Jeśli podano odpowiednie słowo. Rozwiążę moją odpowiedź.

Blue Magister

Proszę, spróbuj teraz. Nie jestem pewien, czy mój pompujący lemat jest taki sam jak twój pompujący lemat, więc odwołuję się do Wikipedii .

Blue Magister