Pertanyaan tentang mesin negara dengan tumpukan tunggal untuk memori. Mereka mencirikan kelas bahasa bebas konteks.
Dalam jawaban ini disebutkan Bahasa reguler dapat dikenali oleh otomat terbatas. Bahasa bebas konteks memerlukan tumpukan, dan bahasa sensitif konteks membutuhkan dua tumpukan (yang setara dengan mengatakan itu memerlukan mesin Turing penuh) . Saya ingin tahu tentang kebenaran bagian yang...
Mari kita sebut bahasa bebas konteks deterministik jika dan hanya jika itu dapat diterima oleh otomat push-down deterministik, dan sebaliknya tidak deterministik. Mari kita sebut bahasa bebas konteks secara inheren ambigu jika dan hanya jika semua tata bahasa bebas konteks yang menghasilkan bahasa...
Apakah konteks bahasa berikut ini gratis? L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Seperti yang ditunjukkan oleh sdcvvc, sebuah kata dalam bahasa ini juga...
Diberi tata bahasa bebas konteks G, ada N Nondeterministic Pushdown Automaton yang menerima persis bahasa yang diterima G. (dan sebaliknya) Ada mungkin juga ada sebuah deterministik Pushdown Automaton D yang menerima persis bahasa G menerima juga. Itu tergantung pada tata bahasanya. Dengan...
Saya bertanya-tanya apakah ini bahkan mungkin, karena {anbncn∣n≥0}∉CFL{anbncn∣n≥0}∉CFL\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL} . Oleh karena itu PDA yang dapat membedakan kata w∈{anbncn∣n≥0}w∈{anbncn∣n≥0}w\in\{a^n b^n c^n \mid n \geq 0\} dari sisa {a∗b∗c∗}{a∗b∗c∗}\{a^*b^*c^*\} mungkin...
Masalah apakah dua automat pushdown mengenali bahasa yang sama tidak dapat diputuskan. Masalah apakah automat pushdown mengenali bahasa kosong dapat diputuskan, maka itu juga dapat memutuskan apakah ia mengenali bahasa yang terbatas. Tidak dapat diputuskan apakah bahasa yang diterima oleh otomat...
Saya menyadari automata pushdown non-deterministik dapat menjadi perbaikan daripada yang deterministik karena mereka dapat "memilih" di antara beberapa negara dan ada beberapa bahasa bebas konteks yang tidak dapat diterima oleh pushdown deterministik. Meski begitu, saya tidak mengerti bagaimana...
Meminta saran Raphael tentang titik-temu dua NPDA : Biarkan dan A 2 masing-masing untuk bahasa bebas konteks L 1 dan L 2 . Dengan asumsi kita tahu bahwa L = L 1 ∩ L 2 bebas konteks, dapatkah kita (secara efektif) membuat NPDA A untuk L ?SEBUAH1SEBUAH1A_1SEBUAH2SEBUAH2A_2L1L1L_1L2L2L_2L = L1∩...
Saya ingin mengubah pengguna memasukkan ekspresi reguler ke NFA sehingga saya kemudian dapat menjalankan NFA terhadap string untuk tujuan yang cocok. Apa mesin minimum yang dapat digunakan untuk mem-parsing ekspresi reguler? Saya menganggap itu harus berupa push down automaton karena keberadaan...
Di tempat kerja saya ditugaskan untuk menyimpulkan beberapa jenis informasi tentang bahasa yang dinamis. Saya menulis ulang urutan pernyataan menjadi letekspresi bersarang , seperti: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z =>...
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...
Biarkan string input diberikan sebagai . Kemudian jika NFA saat ini dalam keadaan r (dan telah membaca input hingga alfabet w i ) maka sebelum membaca simbol input berikutnya NFA terbagi menjadi dua NFA, satu berada di keadaan r dan yang lainnya di s , jika ada transisi dari tipe r ϵ → s . Jika ada...
Apakah ada seperangkat aturan atau metode untuk mengubah tata bahasa bebas konteks apa pun menjadi automata push down? Saya sudah menemukan beberapa slide online tetapi saya tidak dapat memahaminya. Dalam slide 10 dia berbicara tentang beberapa aturan, adakah yang bisa
Slide kuliah ini membuat sketsa bukti ituL={anbn∣n≥0}∪{anb2n∣n≥0}L={anbn∣n≥0}∪{anb2n∣n≥0}L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \} tidak dapat diterima oleh Deterministic Pushdown Automaton. Sayangnya, slide tidak memberikan referensi ke mana bukti itu berasal. Saya...
Tentukan kesetaraan Nerode di atas bahasa sebagai iff untuk setiap .L⊆Σ∗L.⊆Σ∗L \subseteq \Sigma^{*}u∼Lvkamu∼L.vu \sim_L vuw∈L⇔vw∈Lkamuw∈L.⇔vw∈L.uw \in L \Leftrightarrow vw \in Lw∈Σ∗w∈Σ∗w \in \Sigma^{*} Nerode ekivalen memiliki banyak kelas ekivalensi tepat ketika dapat dikenali oleh otomat...
Apakah bahasa bebas konteks?L={0n1m∣n and m are co-prime}L={0n1m∣n and m are co-prime} L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\} Saya kira itu bukan konteks bebas karena tampaknya terlalu rumit untuk PDA untuk memutuskan apakah 2 angka adalah co-prime atau tidak. Saya mencoba...
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...
Menurut grafik ini , DCFL ditutup di bawah pembalikan. Namun, saya tidak yakin sebagai bukti intuitif (membalikkan panah dari mesin negara hingga dan mengalihkan dorongan dan muncul) untuk ini tampaknya tergantung pada non-determinisme dalam memilih transisi nol untuk mengambil dari keadaan awal...
Apakah mungkin untuk meminimalkan automata pushdown? Jika tidak, mengapa? Apakah karena untuk minimalisasi, kelas ekivalensi perlu memiliki indeks yang terbatas dan kami tidak dapat menjaminnya untuk
Biarkan A={L∣Lis one-counter and L¯ is also one-counter}A={L∣Lis one-counter and L¯ is also one-counter}A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \} Jelas,Deterministic one-counter⊆ADeterministic one-counter⊆A\text{Deterministic one-counter} \subseteq A Apakah ini...