Pertanyaan yang diberi tag closure-properties

Bahasa bebas konteks tidak ditutup di bawah pelengkap, kami tahu itu. Sejauh yang saya mengerti, bahasa bebas konteks yang merupakan bagian dari a∗b∗a∗b∗a^*b^* untuk beberapa huruf a,ba,ba,b ditutup di bawah pelengkap (!?) Inilah argumen saya. Setiap bahasa CF LLL memiliki gambar Parikh...

Ini adalah pertanyaan tindak lanjut dari yang satu ini . Dalam pertanyaan sebelumnya tentang mesin negara eksotis , Alex ten Brink dan Raphael membahas kemampuan komputasi dari jenis mesin negara yang aneh: min-heap automata. Mereka mampu menunjukkan bahwa himpunan bahasa yang diterima oleh mesin...

Biarkan GGG menjadi tata bahasa bebas konteks. Serangkaian terminal dan nonterminals dari GGG dikatakan menjadi bentuk sentensial dari GGG jika Anda bisa mendapatkannya dengan menerapkan produksi dari GGG nol atau beberapa kali untuk simbol awal SSS . Mari SF(G)SF⁡(G)\operatorname{SF}(G) adalah...

adalah bahasa reguler di atas alfabet Σ = { a , b } . Hasil bagi kiri L mengenai w ∈ Σ ∗ adalah bahasa w - 1 L : = { v ∣ w v ∈ L }LLLΣ = { a , b }Σ={Sebuah,b}\Sigma = \{a,b\}LLLw ∈ Σ∗w∈Σ∗w \in \Sigma^*w- 1L : = { v ∣ w v ∈ L }w-1L: ={v∣wv∈L}w^{-1} L := \{v \mid wv \in L\} Bagaimana saya bisa...

Saya sangat suka bantuan Anda dengan yang berikut: Untuk setiap tetap saya perlu untuk memutuskan apakah ada penutupan di bawah operator berikut:L2L2L_2 Ar(L)={x∣∃y∈L2:xy∈L}Ar(L)={x∣∃y∈L2:xy∈L}A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\} Al(L)={x∣∃y∈L:xy∈L2}Al(L)={x∣∃y∈L:xy∈L2}A_l(L)=\{x \mid...

Apakah ada bahasa yang tidak dapat ditentukan sehingga bahasa gabungan / persimpangan / bahasa bersatu mereka dapat ditentukan? Apa interpretasi fisik dari contoh seperti itu karena secara umum, bahasa yang tidak dapat ditentukan tidak ditutup dalam operasi ini? Apa yang bisa kita katakan tentang...

Saya telah menemukan pertanyaan itu: "Berikan contoh dua bahasa biasa yang tidak disatukan oleh bahasa mereka dengan bahasa biasa." Ini cukup mengejutkan bagi saya karena saya percaya bahwa bahasa reguler ditutup di bawah persatuan. Yang berarti bagi saya bahwa jika saya mengambil dua bahasa...

Saya ingin membuktikan bahwa komplemen dari tidak biasa menggunakan properti penutupan.{ 0n1n∣ n ≥0 }{0n1n∣n≥0}\{0^n1^n \mid n \geq{} 0\} Saya mengerti memompa lemma dapat digunakan untuk membuktikan bahwa bukan bahasa biasa. Saya juga mengerti bahasa reguler ditutup di bawah operasi pelengkap....

Jika A2A2A^2 teratur, apakah itu mengikuti bahwa AAA teratur? Upaya saya pada bukti: Ya, untuk kontradiksi anggaplah bahwa AAA tidak teratur. Kemudian A2=A⋅AA2=A⋅AA^2 = A \cdot A . Karena penggabungan dua bahasa non-reguler adalah tidak biasa, A2A2A^2 tidak dapat teratur. Ini bertentangan...

Satu dapat memahami pertanyaan Anda dalam dua cara, sesuai dengan definisi "pelengkap CFL". kasus A: Komplemen CFL adalah kelas dari semua bahasa yang tidak ada dalam CFL. Secara formal, Dalam hal ini, jauh lebih besar dari , bahkan memiliki bahasa yang tidak ada dalam , dll. Tapi mungkin bukan...

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

Salah satu cara melihat ekspresi reguler adalah sebagai bukti konstruktif dari fakta berikut: adalah mungkin untuk membangun bahasa reguler dengan memulai dengan sekelompok kecil bahasa dan menggabungkannya melalui set kecil, properti penutupan tertutup. Khususnya, jika kita mulai dengan bahasa...

Saya terjebak menyelesaikan latihan berikutnya: Berargumen bahwa jika bebas konteks dan teratur, maka (yaitu hasil bagi yang tepat ) bebas konteks.R L / R = { w ∣ ∃ x ∈ RL.LLRRRL / R = { w ∣ ∃ x ∈ Rstw x ∈ L }L/R={w∣∃x∈Rs.twx∈L}L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} Saya...

Saya telah membaca beberapa makalah teori bahasa formal, dan saya menemukan istilah yang tidak saya mengerti. Makalah ini akan sering merujuk pada satu set yang "ditutup secara efektif di bawah persimpangan" atau operasi lainnya. Apa arti "efektif" di sini? Apa bedanya dengan penutupan...

Di kelas minggu ini kita telah belajar tentang CFL dan properti penutupannya. Saya telah melihat bukti untuk persatuan, persimpangan dan pujian tetapi untuk pembalikan dosen saya hanya mengatakan itu ditutup. Saya ingin melihat buktinya jadi saya sudah mencari selama beberapa hari terakhir, tetapi...

Saya telah mencoba cukup lama untuk menemukan konstruksi sehingga saya dapat secara resmi menunjukkan bahwa PDA deterministik ditutup dengan komplementasi. Namun, kebetulan setiap ide yang saya dapatkan memiliki sesuatu yang pada akhirnya tidak cocok. Bisakah Anda membantu saya? Masalah utama...

Biarkan menjadi bahasa biasa. Apakah bahasa teratur?LLLL2={y:∃x,z  s.t.|x|=|z| and xyz∈L}L2={y:∃x,z  s.t.|x|=|z| and xyz∈L}L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \} Saya tahu ini sangat mirip dengan pertanyaan di sini , tetapi yang menarik adalah bahwa itu bukan substring...

Kami memiliki dua bahasa: . Kami tahu bahwa adalah bahasa biasa, jadi pertanyaan saya adalah apakah biasa untuk?L.1,L.2L1,L2L_1,L_2L.1L.2L1L2L_1L_2L.2L.1L2L1L_2L_1 Saya mencoba mencari cara untuk membuktikannya ... Tentu saja saya tidak dapat berasumsi bahwa teratur ... Jadi saya mencari cara...

Jadi saya sudah menggaruk-garuk kepala karena masalah ini selama beberapa hari sekarang. Diberi beberapa bahasaAAAdan yang teratur, menunjukkan bahwa bahasa yang terdiri dari semua string dalam yang panjangnya sama dengan beberapa string dalam adalah bahasa biasa.BBBLLLAAABBB Dalam bentuk...

Saya mendapat ujian beberapa hari dan memiliki masalah untuk menyelesaikan tugas ini. Membiarkan LLL menjadi bahasa biasa di atas alfabet ΣΣ\Sigma. Kami memiliki operasi cycle(L)={xy∣x,y∈Σ∗ and yx∈L}cycle⁡(L)={xy∣x,y∈Σ∗ and yx∈L}\operatorname{cycle}(L) = \{ xy \mid x,y\in \Sigma^* \text{ and }...