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

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

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

fl.formal-languages grammars context-free jerr18
źródło

Pytanie również na math.stackexchange. Ma na myśli: czy istnieje sekwencja permutacji tak że języki masz wielomianowe CFG?

π_{1}^{n}, π_{2}^{n} \in S_{n}

$\pi_1^n,\pi_2^n \in S_n$

L_{n} = {w π_{1} (w) π_{2} (w) : w \in {0, 1}^{n}}

$L_n = \{w \pi_1(w) \pi_2(w) : w\in \{0,1\}^n\}$

Yuval Filmus

math.stackexchange.com/questions/22361/…

Tsuyoshi Ito

Czy wiemy, czy istnieje CFG dla ?

L = ⋃_{n} L_{n}

$L = \bigcup_n L_n$

Kaveh

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

L

$L$

p

$p$

w = 0^{p} 1^{p}

$w = 0^p 1^p$

L_{n}

$L_n$

Ω (n / \log n)

$\Omega(n / \log n)$

3 n

$3n$

L_{n}

$L_n$

> 3 n

$> 3n$

Joshua Grochow

@Kaveh: (Również jeśli sekwencja perms może być wybrana arbitralnie, to twój język

L

$L$ nie muszą nawet być obliczalne ... OQ wydaje się z natury niejednolity.)

Joshua Grochow

Chomsky normalna forma

CFG jest w CNF (normalnej formie Chomsky'ego), jeśli tylko produkcje są w tej formie $A \rightarrow a$ i ; gramatyka może być przeniesiona do CNF tylko z kwadratowym powiększeniem. $A \rightarrow BC$

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 . $G$ $G$ $w$ $\ell \leq w$ $x$ $w$ $\ell/2 \leq |x| < \ell$ $G$ $\ell$ $\ell/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 . $L_n$ $\pi_1,\pi_2 \in S_n$ $L_n$ $w(x) = x\pi_1(x)\pi_2(x)$ $x \in \{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)$

\frac{n}{2} \leq | s (x) | < n

$\frac{n}{2} \leq |s(x)| < n$

A (x)

$A(x)$

p (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)|<n$ $s(x)$ $x$ $\pi_2(x)$ $w(x)$ $x$ $w(x)$ $x \alpha s(x) \beta$ $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)$ $\pi_1(y)$ $\pi_2(y)$ $n/4$ $n/4$ $y$ $2^{3n/4}$ $y \in \{0,1\}^n$ $p(x) = p(y)$ $A(x) = A(y)$ $3n$ $p(y)$

\frac{2^{n / 4}}{3 n}

$\frac{2^{n/4}}{3n}$

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 . $\pi_1,\pi_2 \in S_{\{0,1\}^n}$ $n$ $n/4$ $\pi_i(y)$ $2^{3n/4}$ $y$

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). $\mathbb{N}$ $0$ $\mathbb{N}_{\geq 1}$

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

Yuval Filmus
źródło

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

Jest taki napis: cs.toronto.edu/~yuvalf/cfg.pdf .

Yuval Filmus

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 ?

N_{\geq 1}

$N_{\geq 1}$

Σ^{| Σ |}

$\Sigma^{|\Sigma|}$

jerr18

Zobacz powiązane pytanie cstheory.stackexchange.com/q/5014, gdzie Yuval opublikował odpowiedź z opublikowanym odniesieniem.

András Salamon

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

Odpowiedzi:

Chomsky normalna forma

Rozwiązanie

Więcej przykładów