Czy istnieją permutacje i wielkość wielomianowa (w ) gramatyka bezkontekstowa opisująca język skończony zamiast alfabetu ?
AKTUALIZACJA: Dla jednej permutacji jest to możliwe. jest odwróceniem lub względnie niewielką modyfikacją odwrócenia.
Czy istnieją permutacje i wielkość wielomianowa (w ) gramatyka bezkontekstowa opisująca język skończony zamiast alfabetu ?
AKTUALIZACJA: Dla jednej permutacji jest to możliwe. jest odwróceniem lub względnie niewielką modyfikacją odwrócenia.
Odpowiedzi:
CFG jest w CNF (normalnej formie Chomsky'ego), jeśli tylko produkcje są w tej formie i ; gramatyka może być przeniesiona do CNF tylko z kwadratowym powiększeniem.
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 .
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 .
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 .
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 .
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.
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 .
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).
Byłbym wdzięczny za odniesienie do tej metody dowodu.