Apakah ada CFG ukuran polinomial yang menjelaskan bahasa terbatas ini?

Apakah ada permutasi dan ukuran polinomial (dalam ) konteks tata bahasa gratis yang menggambarkan bahasa hingga lebih dari alfabet ?$\pi_1,\pi_2$$|w|=n$$\{w \pi_1(w) \pi_2(w)\}$$\{0,1\}$

PEMBARUAN: Untuk satu permutasi $\pi$ dimungkinkan. $\pi$ adalah pembalikan atau modifikasi pembalikan yang relatif kecil.

Bentuk normal Chomsky

CFG dalam CNF (bentuk normal Chomsky) jika satu-satunya produksi adalah bentuk dan ; tata bahasa dapat dibawa ke CNF dengan hanya blowup kuadratik.A → B $A \rightarrow a$$A \rightarrow BC$

Untuk tata bahasa di CNF, kita memiliki bagus Subword Lemma: Jika menghasilkan kata , maka untuk setiap , ada subword dari panjang yang dihasilkan oleh beberapa non-terminal . Bukti: Turunkan pohon sintaks (biner), selalu ke anak yang menghasilkan subword yang lebih panjang. Jika Anda mulai dengan subword dengan ukuran setidaknya , Anda tidak mungkin masuk di bawah .G w ℓ ≤ w x w ℓ / 2 ≤ | x | < ℓ G ℓ ℓ /$G$$G$$w$$\ell \leq w$$x$$w$$\ell/2 \leq |x| < \ell$$G$$\ell$$\ell/2$

Larutan

Tanpa kehilangan umum, kita dapat mengasumsikan bahwa tata bahasa untuk (bahasa seperti itu dengan ) adalah dalam Bentuk Normal Chomsky. Bahasa terdiri dari kata untuk semua .π 1 , π 2 ∈ S n L n w ( x ) = x π 1 ( x ) π 2 ( x ) x ∈ { 0 , 1 } $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$

Menggunakan Subword Lemma, untuk setiap kita dapat menemukan substring panjangnya dihasilkan oleh beberapa simbol dan terjadi pada posisi .s ( x ) $w(x)$$s(x)$A(x)p(x

Misalkan dan . Karena , subword tidak dapat memotong bagian dan bagian dari ; kita dapat menganggapnya terpisah dari bagian . Jadi adalah dari bentuk . Ini menyiratkan bahwa menghasilkan tepat satu string, yaitu . Karena itu .A ( x ) = A ( y ) | s ( x ) | < n s ( x ) x π 2 ( x ) w ( x ) x w ( x ) x α s ( x ) β A ( x ) s ( x ) $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)$

Sekarang memotong atau setidaknya di tempat, dan dengan demikian menentukan setidaknya bit . Oleh karena itu paling banyak string dapat memiliki dan . Karena ada paling banyak kemungkinan untuk , kita dapatkan bahwa setidaknya ada non-terminal berbeda dalam tata bahasa.π 1 ( y ) π 2 ( y ) n / 4 n / 4 y 2 3 n / 4 y ∈ { 0 , 1 } n p ( x ) = p ( y ) A ( x ) = A ( y ) 3 n p ( y ) 2 n $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)$

Komentar: Bukti yang sama berfungsi jika , yaitu permutasi acak pada set semua kata-kata bit. Diberikan bit dari , ada persis preimages . n n / 4 π i ( y ) 2 3 n / 4$\pi_1,\pi_2 \in S_{\{0,1\}^n}$$n$$n/4$$\pi_i(y)$$2^{3n/4}$$y$

Lebih banyak contoh

Dengan menggunakan metode yang sama, seseorang dapat membuktikan bahwa bahasa tempat setiap karakter muncul tepat dua kali membutuhkan CFG ukuran eksponensial dalam ukuran alfabet. Kita dapat mengganti "dua kali" dengan subset dari selain dari empat yang sepele (mengabaikan , baik yang tidak mengandung atau semuanya). 0 N ≥ $\mathbb{N}$$0$$\mathbb{N}_{\geq 1}$

Saya akan sangat menghargai referensi untuk metode bukti ini.