Bukti mudah untuk bahasa bebas konteks ditutup di bawah pergantian siklik

The pergeseran siklik (juga disebut rotasi atau konjugasi ) dari bahasa didefinisikan sebagai { y x | x y ∈ L } . Menurut wikipedia (dan di sini$L$$\{ yx \mid xy \in L \}$ ) bahasa bebas konteks ditutup di bawah operasi ini, dengan referensi ke makalah dari Oshiba dan dari Maslov. Apakah ada bukti mudah dari fakta ini?

Untuk bahasa reguler penutupan dibahas dalam formulir ini sebagai " Buktikan bahwa bahasa reguler ditutup di bawah operator siklus ".

Anda dapat mencoba menggunakan automata pushdown. Diberi otomat pushdown untuk bahasa asli, kami membuat satu untuk pergantian siklik. Otomat baru beroperasi dalam dua tahap, sesuai dengan bagian dan x dari kata y x (di mana x y dalam bahasa aslinya). Pada tahap pertama, setiap kali otomat ingin pop non-terminal A , itu malah bisa mendorong non-terminal A ' ; idenya adalah bahwa pada akhir tahap pertama, tumpukan akan berisi, dalam urutan terbalik, simbol-simbol yang ditemukan dalam tumpukan setelah membaca $y$$x$$yx$$xy$$A$$A'$$x$oleh robot asli. Pada tahap kedua (sakelar non-deterministik), alih-alih mendorong non-terminal , kita diizinkan untuk mengeluarkan non-terminal A ′ . Jika automaton asli memang dapat menghasilkan stack setelah membaca x , maka yang baru akan dapat persis pop seluruh stack.$A$$A'$$x$

Sunting: Berikut adalah beberapa detail lainnya. Misalkan kita diberi PDA dengan alfabet , set status Q , set status penerimaan F , non-terminal Γ , status awal q 0 , dan serangkaian transisi yang diizinkan. Setiap transisi yang diijinkan adalah dari bentuk ( q , a , A , q ′ , α ) , yang berarti bahwa ketika dalam keadaan q , setelah membaca a ∈ A (atau a = ϵ , dalam hal ini adalah transisi bebas), jika bagian atas -of-stack adalah A $\Sigma$$Q$$F$$\Gamma$$q_0$$(q,a,A,q',\alpha)$$q$$a \in A$$a = \epsilon$.$A \in \Gamma$(atau , yang berarti tumpukan kosong), maka PDA dapat (ini adalah model non-deterministik) pindah ke status q ′ , menggantikan A dengan α ∈ Γ $A = \epsilon$$q'$$A$$\alpha \in \Gamma^*$

PDA baru memiliki non-terminal baru untuk setiap A ∈ Γ . Untuk setiap dua status q , q ′ ∈ Q dan A ∈ Γ ∪ { ϵ } , ada dua status ( q , q ′ , 1 ) , ( q , q ′ , 2 , A ) . Status awal (kondisi awal aktual dipilih secara non-deterministik di antara mereka melalui transisi ϵ ) adalah$A'$$A \in \Gamma$$q,q' \in Q$$A \in \Gamma \cup \{\epsilon\}$$(q,q',1),(q,q',2,A)$$\epsilon$ . Untuk setiap transisi ( q , a , A , q ′ , α ) ada transisi yang sesuai ( ( q , q ″ , 1 ) , a , A , ( q ′ , q ″ , 1 ) , α ) dan ( ( q , q ″ , 2 , $(q,q,1)$$(q,a,A,q',\alpha)$$((q,q'',1),a,A,(q',q'',1),\alpha)$. Ada transisi lain juga.$((q,q'',2,B),a,A,(q',q'',2,B),\alpha)$

Untuk setiap transisi , ada transisi ( ( q , q ″ , 1 ) , a , B ′ , ( q ′ , q ″ , 1 ) , B ′ A ′ α ) , di mana B ∈ Γ ∪ { ϵ } dan ϵ ′$(q,a,A,q',\alpha)$$((q,q'',1),a,B',(q',q'',1),B'A'\alpha)$$B \in \Gamma \cup \{\epsilon\}$$\epsilon' = \epsilon$. Untuk setiap keadaan akhir , ada transisi ( ( q , q ″ , 1 ) , ϵ , A , ( q 0 , q ″ , 2 , ϵ ) , A ) , di mana A ∈ Γ ∪ { ϵ $q \in F$$((q,q'',1),\epsilon,A,(q_0,q'',2,\epsilon),A)$$A \in \Gamma \cup \{\epsilon\}$ .

Untuk setiap transisi , ada transisi ( ( q , q ″ , 2 , A ) , a , B ′ , ( q ′ , q ″ , 2 , A ) , B ′ α ) , di mana A ∈ Γ ∪ { ϵ } . Untuk setiap transisi$(q,a,\epsilon,q',\alpha)$$((q,q'',2,A),a,B',(q',q'',2,A),B'\alpha)$$A \in \Gamma \cup \{\epsilon\}$ , ada transisi ( ( q , q ″ , 2 , B ) , a , A ′ , ( q ′ , q ″ , 2 , A ) , ϵ ) , di mana B ∈ Γ ∪ { ϵ } . Untuk setiap transisi ( q , $(q,a,\epsilon,q',A)$$((q,q'',2,B),a,A',(q',q'',2,A),\epsilon)$$B \in \Gamma \cup \{\epsilon\}$ , , ada "transisi umum" ( ( q , q ″ , 2 , C ) , a , B ′ A , ( q , q ″ , 2 , C ) , ϵ ) ; ini diimplementasikan sebagai urutan dua transisi melalui negara baru menengah. Transisi ( q , a , ϵ , q ′ α ) dengan$(q,a,A,q',B)$$((q,q'',2,C),a,B'A,(q,q'',2,C),\epsilon)$$(q,a,\epsilon,q',\alpha)$ ditangani dengan cara yang sama. Untuk setiap transisi ( q , a , A , q ′ , A ) , ada transisi ( ( q , q ″ , 2 , A ) , a , B , ( q ′ , q ″ , 2 , A ) , B ) , dimana B $|\alpha| \geq 2$$(q,a,A,q',A)$$((q,q'',2,A),a,B,(q',q'',2,A),B)$ . Transisi ( q , a , A , q ′ , A α ) ditangani dengan cara yang sama. Akhirnya, ada satu-satunya kondisi akhir f , dan transisi ( ( q , q , 2 , A ) , ϵ , ϵ , f , ϵ ) .$B \in \Gamma' \cup \{\epsilon\}$$(q,a,A,q',A\alpha)$$f$$((q,q,2,A),\epsilon,\epsilon,f,\epsilon)$

(Mungkin ada beberapa transisi yang saya lewatkan, dan beberapa detail yang saya hilangkan agak berantakan.)

Ingat, kami mencoba menerima kata , di mana x y diterima oleh PDA asli. Status ( q , q ′ , 1 ) berarti kita berada pada tahap 1, pada keadaan q , dan PDA asli berada pada keadaan q ′ setelah membaca x . Sebuah negara ( q , q ' , 2 , A ) adalah serupa, di mana A berkorespondensi untuk yang terakhir A ' yang muncul. Pada tahap 1, kita diizinkan untuk mendorong A $yx$$xy$$(q,q',1)$$q$$q'$$x$$(q,q',2,A)$$A$$A'$$A'$bukannya bermunculan . Kami melakukan itu untuk setiap non-terminal yang diproduksi saat memproses x , tetapi hanya muncul saat memproses y . Pada tahap 2, kita diperbolehkan untuk pop A ' bukannya mendorong A . Jika kita melakukan ini, maka kita harus ingat bahwa persediaan tertinggi adalah A ; ini hanya berlaku ketika tidak ada hal-hal "sementara" pada stack, yang dalam simulasi PDA adalah sama dengan top-of-stack menjadi ϵ atau dari bentuk B ′ .$A$$x$$y$$A'$$A$$A$$\epsilon$$B'$

Ini adalah contoh sederhana. Pertimbangkan otomat untuk yang mendorong A untuk setiap x , dan muncul A untuk setiap y . Otomat baru menerima kata-kata dari dua bentuk: y k x n y n - k dan x k y n x n - k . Untuk kata-kata dari bentuk pertama, tahap 1 terdiri dari mendorong k kali A ′ , tahap 2 terdiri dari muncul k kali A ′ , mendorong $x^n y^n$$A$$x$$A$$y$$y^k x^n y^{n-k}$$x^k y^n x^{n-k}$$k$$A'$$k$$A'$ kali A , dan muncul n - k kali A . Untuk kata-kata dari bentuk kedua, pertama-tama kita mendorong k kali A , lalu pop k kali A , mendorong n - k kali A ′ , transisi ke tahap 2, dan pop n - k kali A $n-k$$A$$n-k$$A$$k$$A$$k$$A$$n-k$$A'$$n-k$$A'$ .

Berikut adalah contoh yang lebih rumit, untuk bahasa kurung yang seimbang dari berbagai jenis ("()", "[]", "<>") sehingga keturunan langsung dari masing-masing jenis kurung harus berasal dari jenis yang berbeda. Misalnya, "([] <>)" tidak apa-apa tapi "()" salah. Untuk setiap "(", kita mendorong jika top-of-stack tidak A , untuk setiap ")", kami pop A . Demikian pula B , C dikaitkan dengan "[]" dan "<>". Inilah cara kami menerima kata ">) ([()] <". Kami mengonsumsi ">)", mendorong C ′ A ′ , dan beralih ke tahap 2. Kami mengonsumsi "(", bermunculan A ' dan mengingat top-of-stack A . Kami mengkonsumsi "[()]", mendorong dan muncul$A$ $A$$A$$B$$C$$C'A'$$A'$$A$ ; ketika mendorong$BA$ , kami menyadari bahwa top-of-stack "nyata" adalah A , dan kurung kotak diperbolehkan (kami tidak akan tertipu oleh ">) (() <"); ketika mendorong A , karena top-of-stack adalah B (yang bukan ϵ atau dari bentuk X ′ ), maka kita tahu bahwa B juga merupakan top-of-stack "nyata", sehingga tanda kurung bundar diperbolehkan ( meskipun shadow top-of-stack adalah A ). Akhirnya, kita mengkonsumsi "<" dan pop C ′ .$B$$A$$A$$B$$\epsilon$$X'$$B$$A$$C'$

Pertimbangkan bentuk normal Greibach . Untuk membangun sebuah bahasa bergeser Anda hanya perlu produksi perubahan untuk S → A 1 ... A n α dan menambahkan non-terminal baru S ' yang berperilaku seperti S digunakan untuk, dalam beberapa kasus beberapa produksi dirujuk S .$S \to \alpha A_1 \dots A_n$$S \to A_1\dots A_n \alpha$$S'$$S$$S$

Ternyata menjadi ide yang bagus untuk memeriksa Pengantar klasik Hopcroft dan Ullman klasik ke Teori Automata (1979). Penutupan di bawah siklus adalah Latihan 6.4c dan ditandai S **. Bintang ganda berarti itu adalah salah satu masalah yang paling sulit (dalam buku ini). Untungnya S menunjukkan itu adalah salah satu masalah yang dipilih dengan solusi.

$S=X_1, X_2, \dots , X_n$$x_1, x_2, \dots, x_n$$y_1, y_2, \dots, y_n$$x_1 x_2 \dots x_n y_n \dots y_2 y_1$$x_i$

$S', \hat X_n, \dots \hat X_2, \hat X_1$$y_n, \dots, y_2 y_1$$x_n, \dots, x_2 x_1$$y_n \dots y_2 y_1 x_1 x_2 \dots x_n$

Rincian lengkap konstruksi diberikan dalam buku ini.

Perhatikan bagaimana ini mengingatkan solusi (diterima) oleh Yuval. Nonterminals yang didorong bukannya muncul berada dalam urutan yang berlawanan pada stack. Cukup mirip terbalik di pohon.