Pertanyaan tentang sekumpulan bahasa (setara) yang dijelaskan oleh tata bahasa bebas konteks atau diterima oleh automata pushdown (non-deterministik).
Ada banyak definisi online tentang apa itu Tata Bahasa Bebas Konteks, tetapi tidak ada yang saya temukan yang memuaskan masalah utama saya: Konteks apa itu gratis? Untuk menyelidiki, saya mencari "tata bahasa sensitif konteks" di Google, tetapi saya masih gagal menemukan apa arti "konteks"...
Saya telah mempelajari kompiler untuk sementara waktu, dan saya telah mencari apa yang dimaksud dengan "konteks" dalam tata bahasa dan apa artinya bagi tata bahasa untuk menjadi "bebas konteks", tetapi tanpa hasil. Jadi, adakah yang bisa membantu dengan
Saya memiliki satu set pasangan. Setiap pasangan berbentuk (x, y) sedemikian rupa sehingga x, y milik bilangan bulat dari kisaran [0,n). Jadi, jika n adalah 4, maka saya memiliki pasangan berikut: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Saya sudah memiliki pasangan. Sekarang, saya harus membangun...
Ada banyak teknik untuk membuktikan bahwa bahasa adalah tidak bebas konteks, tapi bagaimana saya membuktikan bahwa bahasa adalah bebas konteks? Teknik apa yang ada untuk membuktikan ini? Jelas, salah satu caranya adalah dengan menunjukkan tata bahasa bebas konteks untuk bahasa tersebut. Apakah ada...
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...
Masalah saya adalah bagaimana saya bisa membuktikan bahwa tata bahasa tidak ambigu? Saya memiliki tata bahasa sebagai berikut: S→statement∣if expression then S∣if expression then S else SS→statement∣if expression then S∣if expression then S else SS → statement ∣ \mbox{if } expression \mbox{ then }...
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...
Ketika mempertimbangkan model mesin dari perhitungan, hierarki Chomsky biasanya ditandai oleh (dalam urutan), automata terbatas, automata push-down, automata terikat linier dan Mesin Turing. Untuk level pertama dan terakhir 1 (bahasa reguler dan bahasa yang berulang secara berulang), tidak ada...
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...
Mari kita pertimbangkan dua tata bahasa bebas konteks dan G 2 dan tanyakan pertanyaan berikut: Apakah L ( G 1 ) = L ( G 2 ) , yaitu, apakah kedua tata bahasa setara?G1G1G_1G2G2G_2L ( G1) = L ( G2)L.(G1)=L.(G2)L(G_1) = L(G_2) Secara umum, masalah ini tidak dapat dipastikan. Namun, jika kedua dan G...
Apakah ada algoritma / prosedur sistematis untuk menguji apakah suatu bahasa bebas konteks? Dengan kata lain, diberikan bahasa yang ditentukan dalam bentuk aljabar (pikirkan sesuatu seperti ), uji apakah bahasa tersebut bebas konteks atau tidak. Bayangkan kita sedang menulis layanan web untuk...
Bisakah tata bahasa bebas konteks menyertakan "keadaan mati" dari otomat, seperti G = ( { a , b , c } , { A , B , C} , { A → a B , B → b , B → C, C→ c C} , A )?G=({Sebuah,b,c},{SEBUAH,B,C},{SEBUAH→SebuahB,B→b,B→C,C→cC},SEBUAH)?G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to...
Perhatikan bahwa ini adalah pertanyaan yang terkait dengan belajar di kursus CS di universitas, BUKAN pekerjaan rumah dan dapat ditemukan di sini di bawah ujian Musim Gugur 20112. Inilah dua pertanyaan yang saya lihat dari ujian sebelumnya. Mereka tampaknya terkait, yang pertama: Membiarkan...
Perpotongan bahasa bebas konteks L dengan bahasa reguler M, dikatakan selalu bebas konteks. Saya memahami bukti konstruksi produk silang, tetapi saya masih belum mengerti mengapa ini bebas konteks tapi tidak teratur. Bahasa yang dihasilkan oleh persimpangan semacam itu memiliki string yang...
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...
Jadi pada dasarnya L memenuhi kondisi lemma pemompaan untuk CFL tetapi bukan CFL (itu mungkin menurut definisi
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...
Saya tahu bahwa ada bahasa non-reguler, sehingga teratur, tetapi semua contoh yang saya temukan adalah peka konteks tetapi tidak bebas konteks.L∗L∗L^* Jika tidak ada, bagaimana Anda
Saya mencoba memahami apa yang dimaksud dengan "deterministik" dalam ungkapan seperti "tata bahasa bebas konteks deterministik". (Ada lebih banyak "hal-hal" deterministik dalam bidang ini). Saya akan menghargai contoh lebih dari penjelasan yang paling rumit! Jika memungkinkan. Sumber kebingungan...
Saya punya masalah dengan latihan ini: Biarkan G menjadi tata bahasa ambigu berikut untuk kalkulus λ: E → v | λv.E | EE | (E) di mana E adalah simbol non-terminal tunggal, λv.E mewakili abstraksi dari variabel v di E, dan EE mewakili aplikasi. Definisikan tata bahasa LL (1) G ′...