Czy istnieje wielomianowy rozmiar CFG opisujący ten skończony język?


9

Czy istnieją permutacje i wielkość wielomianowa (w ) gramatyka bezkontekstowa opisująca język skończony zamiast alfabetu ?π1,π2|w|=n{wπ1(w)π2(w)}{0,1}

AKTUALIZACJA: Dla jednej permutacji jest to możliwe. jest odwróceniem lub względnie niewielką modyfikacją odwrócenia.ππ


5
Pytanie również na math.stackexchange. Ma na myśli: czy istnieje sekwencja permutacji tak że języki masz wielomianowe CFG? π1n,π2nSnLn={wπ1(w)π2(w):w{0,1}n}
Yuval Filmus


1
Czy wiemy, czy istnieje CFG dla ? L=nLn
Kaveh

4
@Kaveh: Odpowiedź brzmi nie, dla dowolnej sekwencji perms. Jeśli twój język był pozbawiony kontekstu, to ma on długość pompowania . Zastosuj lemat pompowania dla CFG do łańcucha w L powiązanego z . Lemat pompowania dla CFG również powiedzmy, że jeśli OQ ma pozytywną odpowiedź, to CFG dla musi używać zmiennych co najmniej , ponieważ potrzebujemy aby była mniejsza niż długość pompowania , dzięki czemu nasz CFG dla nie akceptuje żadnych ciągów o długości . Nie wiem jeszcze, jak to wykorzystać, aby wykluczyć pozytywną odpowiedź na OQ, ale może to być możliwe. Lpw=0p1pLnΩ(n/logn)3nLn>3n
Joshua Grochow

1
@Kaveh: (Również jeśli sekwencja perms może być wybrana arbitralnie, to twój język Lnie muszą nawet być obliczalne ... OQ wydaje się z natury niejednolity.)
Joshua Grochow

Odpowiedzi:


13

Chomsky normalna forma

CFG jest w CNF (normalnej formie Chomsky'ego), jeśli tylko produkcje są w tej formie Aai ; gramatyka może być przeniesiona do CNF tylko z kwadratowym powiększeniem.ABC

Dla gramatyki w CNF, mamy ładne podsłowo Lemat: Jeżeli generuje słowo , a następnie dla każdego , istnieje podsłowo stanowi długości , który jest generowany przez pewien brak zacisku . Dowód: zejdź (binarne) drzewo składniowe, zawsze przechodząc do potomka, który generuje dłuższe podmowę. Jeśli zacząłeś od słowa o rozmiarze co najmniej , nie możesz zejść poniżej .GGwwxw/2|x|<G/2

Rozwiązanie

Bez utraty ogólności możemy założyć, że gramatyka dla (taki język ze specyficznym ) ma postać normalną Chomsky'ego. Język składa się ze słów dla wszystkich .Lnπ1,π2SnLnw(x)=xπ1(x)π2(x)x{0,1}n

Używając podmenu Lemma, dla każdego możemy znaleźć podciąg o długości generowany przez jakiś symbol i występujący w pozycji .w(x)s(x)

n2|s(x)|<n
A(x)p(x)

Załóżmy, że i . Ponieważ , podsłowo może nie przecinają zarówno częścią a części ; możemy założyć, że jest on rozłączny od części . Zatem ma postać . Oznacza to, że generuje dokładnie jeden ciąg, a mianowicie . Dlatego .p(x)=p(y)A(x)=A(y)|s(x)|<ns(x)xπ2(x)w(x)xw(x)xαs(x)βA(x)s(x)s(x)=s(y)

Teraz przecina albo albo w co najmniej miejscach, a tym samym określa co najmniej bity . Dlatego najwyżej ciągów może mieć i . Ponieważ istnieje co najwyżej możliwości dla , otrzymujemy, że istnieją co najmniej różne nieterminale w gramatyce.s(y)π1(y)π2(y)n/4n/4y23n/4y{0,1}np(x)=p(y)A(x)=A(y)3np(y)

2n/43n

Komentarz: Ten sam dowód działa, jeśli , tj. Są dowolnymi permutacjami na zbiorze wszystkich bitowych słów. Biorąc pod uwagę bity , istnieją dokładnie preimages .π1,π2S{0,1}nnn/4πi(y)23n/4y

Więcej przykładów

Za pomocą tej samej metody można udowodnić, że język, w którym każdy znak pojawia się dokładnie dwa razy, wymaga CFG wielkości wykładniczej wielkości alfabetu. Możemy „dwukrotnie” zastąpić dowolnym podzbiorem innym niż czterema trywialnymi (ignorując , albo nie zawierającego żadnego z lub wszystkich).N0N1

Byłbym wdzięczny za odniesienie do tej metody dowodu.


2
Yuval, czy mógłbyś również skopiować rozwiązanie tutaj.
Kaveh

Dziękuję Yuval. Jeśli twoja metoda jest poprawna i nowatorska, chętnie przeczytam artykuł badający bardziej ogólne przypadki z pozytywnymi lub negatywnymi wynikami na polisize CFG dla języków skończonych lub nieskończonych.
jerr18


Podejrzewam, że przez wyjątek masz na myśli „przynajmniej jedno wystąpienie terminala”. Czy to oznacza, że ​​możesz wygenerować wszystkie permutacje, przecinając się z ? N1Σ|Σ|
jerr18

1
Zobacz powiązane pytanie cstheory.stackexchange.com/q/5014, gdzie Yuval opublikował odpowiedź z opublikowanym odniesieniem.
András Salamon
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.