Jest uzupełnieniem {ww | …} Bez kontekstu?

15

Zdefiniuj język jako . Innymi słowy, zawiera słowa, których nie można wyrazić jako jakieś słowo powtórzone dwukrotnie. Czy bezkontekstowy czy nie?LL={a,b}{www{a,b}}LL

Próbowałem przeciąć z , ale nadal nie mogę niczego udowodnić. Spojrzałem również na twierdzenie Parikha, ale to nie pomaga.Labab

Jewgienij Eltiszew
źródło
Zwróć uwagę na to ściśle powiązane pytanie .
Raphael

Odpowiedzi:

29

Jest bezkontekstowy. Oto gramatyka:

SA|B|AB|BA
Aa|aAa|aAb|bAb|bAa
Bb|aBa|aBb|bBb|bBa

AGeneruje słowa długości nieparzystej z w centrum. To samo dla i .aBb

Przedstawię dowód, że ta gramatyka jest poprawna. Niech (język w pytaniu).L={a,b}{www{a,b}}

Twierdzenie. . Innymi słowy, ta gramatyka generuje język w pytaniu.L=L(S)

Dowód. To z pewnością odnosi się do wszystkich dziwne długości słów, ponieważ to gramatyka generuje wszystkie nieparzystych długości słowa, podobnie jak . Skupmy się więc na słowach o równej długości.L

Załóżmy, że ma parzystą długość. Pokażę, że . W szczególności twierdzę, że można zapisać w postaci , gdzie zarówno jak i mają nieparzystą długość i różne litery środkowe. Zatem może być pochodzenia lub (w zależności od tego, czy jest centralny litera jest lub ). Uzasadnienie roszczenia: Niech ta litera będzie oznaczona , tak aby . Potem odxLxL(G)xx=uvuvxABBAuabixxix=x1x2xnxnie ma w , musi istnieć jakiś indeks taki, że . W związku z tym możemy wziąć i ; środkowa litera będzie , a środkowa litera będzie , więc ze względu na budowę mają różne środkowe litery.{www{a,b}n/2}ixixi+n/2u=x1x2i1v=x2ixnuxivxi+n/2u,v

Następnie załóżmy, że ma parzystą długość. Pokażę, że musimy mieć . Jeśli ma parzystą długość, musi pochodzić z lub ; bez utraty ogólności, załóżmy, że nie wypływa , a , gdzie jest pochodzących z i można otrzymać drogą . Jeśli mają te same długości, to musimy mieć (ponieważ mają różne środkowe litery), więc . Załóżmy więc,xL(G)xLxABBAABx=uvuAvBu,vuvx{www{a,b}}u,vmają różne długości, powiedzmy odpowiednio długość i . Następnie ich środkowymi literami są i . Fakt, że mają różne środkowe litery, oznacza, że . Ponieważ , oznacza to, że . Jeśli spróbujemy dekomponować jako gdzie mają tę samą długość, wówczas odkryjemy, że , tj. , więcnu(+1)/2v(n+1)/2u,vu(+1)/2v(n+1)/2x=uvx(+1)/2x(n++1)/2xx=www,ww(+1)/2=x(+1)/2x(n++1)/2=w(+1)/2wwx{www{a,b}} . W szczególności, wynika to, że .xL

Jewgienij Eltiszew
źródło
2
Zredagowałem odpowiedź, aby dostarczyć dowód poprawności tej gramatyki, w oparciu o wskazówkę / szkic podaną przez Evgeny Eltishev. Mam nadzieję, że teraz powinno być bardziej zrozumiałe, dlaczego to działa.
DW
Czy może wygenerować „aabb”?
manasij7479
1
@ manasij7479 Tak: . SABaBa(aBb)aabb
J.-E.
3

Ten język jest pozbawiony kontekstu, co zostało udowodnione w następującym artykule:

Tomaszewski, Zach. „Gramatyka bezkontekstowa dla powtarzającego się łańcucha”. Journal of Information and Computer Science , 2012 ( PDF ).

Gramatyka jest następująca:

SEUϵEABBAAZAZaBZBZbUZUZZZab
A. Mashreghi
źródło
8
Witamy! Poniższe nie stanowi krytyki tej odpowiedzi. Journal Informacji i Informatyki został opublikowany przez „Światowego Związku Akademickiego”, który znajduje się na liście Beall za drapieżnych wydawców otwartego dostępu. To smutne, że istnieją firmy na świecie, które podejmą stosunkowo duże kwoty pieniędzy ludzi, aby opublikować artykuły, które nie robią nic więcej, jak rozwiązywać ćwiczenia na poziomie licencjackim.
David Richerby
Nie mam wystarczającej reputacji, aby skomentować powyższą odpowiedź. Ale ta gramatyka wydaje mi się niewłaściwa. Nie można wygenerować „aaab” w języku.
A. Mashreghi
1
Po wykonaniu (powinieneś spróbować), , więc wygląda na to, że może wygenerować . S B B B b o o bCFGCNFCYKSABaAaBaaaBaaabaaab
Zły
Masz rację
A. Mashreghi