Pertanyaan tentang tata bahasa formal, deskripsi generatif bahasa formal.
Orang sering mengatakan bahwa parser LR (k) lebih kuat daripada parser LL (k) . Pernyataan-pernyataan ini sebagian besar tidak jelas; khususnya, haruskah kita membandingkan kelas untuk tetap atau serikat atas semua ? Jadi bagaimana sebenarnya situasinya? Secara khusus, saya tertarik pada bagaimana...
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...
Melihat bahwa dalam Chomsky Hierarchy Type 3 bahasa dapat dikenali oleh mesin negara tanpa memori eksternal (yaitu, otomat terbatas), Tipe 2 oleh mesin negara dengan tumpukan tunggal (yaitu otomat push-down) dan Tipe 0 oleh mesin negara dengan dua tumpukan (atau, ekuivalen, sebuah kaset, seperti...
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...
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 }...
EPAL, bahasa bahkan palindrom, didefinisikan sebagai bahasa yang dihasilkan oleh tata bahasa bebas konteks berikut: S→aaS→aaS \rightarrow a a S→bbS→bbS \rightarrow b b S→aSaS→aSaS \rightarrow a S a S→bSbS→bSbS \rightarrow b S b EPAL adalah 'kutukan' dari banyak algoritma penguraian:...
Menentukan bahasa formal dengan memberikan tata bahasa formal adalah tugas yang sering: kita membutuhkan tata bahasa tidak hanya untuk menggambarkan bahasa, tetapi juga untuk menguraikannya, atau bahkan melakukan sains yang tepat . Dalam semua kasus, penting bahwa tata bahasa yang ada sudah benar ,...
Pertanyaan ini dimigrasikan dari Theoretical Computer Science Stack Exchange karena dapat dijawab di Computer Science Stack Exchange. Bermigrasi 7 tahun yang lalu . Saya mencari teori matematika yang berhubungan dengan menggambarkan bahasa formal (serangkaian string)
Dalam desain kompiler, mengapa rekursi kiri dihilangkan dalam tata bahasa? Saya membaca bahwa itu karena dapat menyebabkan rekursi yang tak terbatas, tetapi apakah itu tidak benar untuk tata bahasa rekursif yang tepat
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...
Menurut artikel Wikipedia ini , tata bahasa tidak terbatas setara dengan mesin Turing. Artikel tersebut mencatat bahwa saya dapat mengubah mesin Turing apa pun menjadi tata bahasa yang tidak dibatasi, tetapi hanya menunjukkan cara mengubah tata bahasa menjadi mesin Turing. Bagaimana saya melakukan...
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...
Jika saya memiliki Tata Bahasa Tipe 3, itu dapat direpresentasikan pada otomat pushdown (tanpa melakukan operasi apa pun pada stack) sehingga saya dapat mewakili ekspresi reguler dengan menggunakan bahasa bebas konteks. Tapi bisakah saya tahu jika tata bahasa tipe 3 adalah , L L ( 1 ) , S L R ( 1 )...
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...
Dapat diperdebatkan bahwa sebagian besar bahasa yang dibuat untuk menggambarkan masalah sehari-hari bersifat peka konteks. Di sisi lain, adalah mungkin dan tidak sulit untuk menemukan beberapa bahasa yang tidak recursive atau bahkan tidak recursively-enumerable. Di antara kedua jenis ini adalah...
Menurut artikel Wikipedia , L dalam berarti "pemindaian kiri-ke-kanan", dan "R" berarti "derivasi paling kanan." Namun, dalam kertas asli Knuth pada L R ( k ) tata bahasa , ia mendefinisikan L R ( k ) (pada halaman 610) sebagai bahasa yang "diterjemahkan dari kiri ke kanan dengan terikat k ."L R (...
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...