Bagaimana cara membuktikan bahwa tata bahasa tidak ambigu?

25

Masalah saya adalah bagaimana saya bisa membuktikan bahwa tata bahasa tidak ambigu? Saya memiliki tata bahasa sebagai berikut:

Sstatementif expression then Sif expression then S else S

dan membuat ini menjadi tata bahasa yang tidak ambigu, saya pikir itu benar:

  • SS1S2

  • S1if expression then Sif expression then S2 else S1

  • S2if expression then S2 else S2statement

Saya tahu bahwa tata bahasa yang tidak ambigu memiliki satu pohon parse untuk setiap istilah.

pengguna1594
sumber

Jawaban:

20

Ada (setidaknya) salah satu cara untuk membuktikan unambiguity dari tata bahasa G=(N,T,δ,S) untuk bahasa L . Ini terdiri dari dua langkah:

  1. Buktikan LL(G) .
  2. Buktikan [zn]SG(z)=|Ln|.

Langkah pertama cukup jelas: menunjukkan bahwa tata bahasa menghasilkan (setidaknya) kata-kata yang Anda inginkan, itu benar.

Langkah kedua menunjukkan bahwa memiliki banyak pohon sintaks untuk kata-kata dengan panjang seperti memiliki kata-kata dengan panjang - dengan 1. ini mengimplikasikan ketidakjelasan. Ia menggunakan fungsi struktur yang kembali ke Chomsky dan Schützenberger [1], yaitun L n GGnLnG

SG(z)=n=0tnzn

dengan jumlah pohon sintaks yang dimiliki untuk kata-kata panjang . Tentu saja Anda harus memilikiagar ini bekerja.G n | L n |tn=[zn]SG(z)Gn|Ln|

Yang menyenangkan adalah bahwa (biasanya) mudah diperoleh untuk bahasa bebas konteks, walaupun menemukan bentuk tertutup untuk bisa jadi sulit. Ubah menjadi sistem persamaan fungsi dengan satu variabel per nonterminal:t n GSGtnG

[A(z)=(A,a0ak)δ i=0k τ(ai) :AN] with τ(a)={a(z),aNz,aT.

Ini mungkin terlihat menakutkan tetapi sebenarnya hanya transformasi sintaksis seperti yang akan menjadi jelas dalam contoh ini. Idenya adalah bahwa dihasilkan simbol terminal dihitung dalam eksponen dan karena sistem memiliki bentuk yang sama seperti , terjadi sesering dalam penjumlahan sebagai terminal dapat dihasilkan oleh . Periksa Kuich [2] untuk detailnya.G z n n GzGznnG

Memecahkan sistem persamaan ini (aljabar komputer!) Menghasilkan ; sekarang Anda "hanya" harus menarik koefisien (dalam bentuk tertutup, umum). The TCS Cheat Sheet dan komputer aljabar sering dapat melakukannya.S(z)=SG(z)


Contoh

Pertimbangkan tata bahasa sederhana dengan aturanG

SaSabSbε .

Jelas bahwa (langkah 1, bukti dengan induksi). Ada palindrom dengan panjang jika adalah genap, sebaliknya.2 nL(G)={wwRw{a,b}} nn02n2nn0

Menyiapkan hasil sistem persamaan

S(z)=2z2S(z)+1

solusi siapa

SG(z)=112z2 .

Koefisien bertepatan dengan jumlah palindrom, sehingga tidak ambigu. GSG G


  1. Teori Aljabar Bahasa Bebas Konteks oleh Chomsky, Schützenberger (1963)
  2. Tentang entropi bahasa bebas konteks oleh Kuich (1970)
Raphael
sumber
3
Seperti yang Anda ketahui @Raphael, ambiguitas tidak dapat ditentukan, jadi setidaknya salah satu langkah Anda tidak dapat dimekanisasi. Adakah yang tahu? Mendapatkan formulir tertutup untuk ? tn
Martin Berger
2
Sistem persamaan mungkin tidak dapat dipecahkan secara algoritmik jika derajatnya terlalu tinggi, dan menarik koefisien yang tepat dari fungsi-fungsi pembangkit dapat (terlalu) sulit. Dalam "praktek", meskipun, orang sering berurusan dengan tata bahasa "derajat" kecil - perhatikan bahwa, katakanlah, bentuk normal Chomsky mengarah ke sistem persamaan derajat kecil - dan ada metode untuk mendapatkan setidaknya simtotik untuk koefisien; ini mungkin cukup untuk menciptakan ambiguitas. Perhatikan bahwa untuk membuktikan , menunjukkan tanpa menarik koefisien sudah cukup; membuktikan identitas ini mungkin sulit. S L ( z ) = S G ( z )SL(z)=SG(z)
Raphael
@Raphael terima kasih. Apakah Anda tahu ada teks yang berkembang secara terperinci bagaimana ketidakpastian dapat terjadi walaupun ada yang menggunakan misalnya bentuk normal Chomsky? (Saya tidak bisa menghubungi Kuich.)
Martin Berger
@ MartinBerger Saya baru saja menemukan kembali komentar Anda di daftar todo saya; maaf atas kesunyian yang panjang. Ada tiga langkah yang (saya pikir) tidak dapat dihitung secara umum: 1) Tentukan . 2) Hitung. 3) Tentukan . Secara khusus, apa representasi digunakan untuk 2)? | L n | [ Z n ] S g ( z ) LSG|Ln|[zn]Sg(z)L
Raphael
Mengapa representasi merupakan masalah? Kami dapat menggunakan salah satu dari beberapa cara untuk mewakili CFG untuk kompiler misalnya. Mungkin maksud Anda bagaimana mewakili ? LLn
Martin Berger
6

Ini adalah pertanyaan yang bagus, tetapi beberapa Googling akan memberi tahu Anda bahwa tidak ada metode umum untuk memutuskan ambiguitas , jadi Anda perlu membuat pertanyaan Anda lebih spesifik.

reinierpost
sumber
2
OP meminta teknik pembuktian, bukan algoritma.
Raphael
Aku pikir juga begitu; mungkin disebutkan dalam pertanyaan.
reinierpost
1
Google bukan peramal kebenaran, karena pengetahuan tidak demokratis, dan hasilnya Google. Saya tidak akan mengandalkan Google dalam hal ini, karena orang sering menyalin satu sama lain tanpa memeriksa kebenaran dari apa yang mereka salin. Tanpa menunjukkan bukti, mereka mungkin salah.
SasQ
5
@ SasQ: Anda membaca kata-kata saya terlalu harfiah. Apa yang Google berikan kepada saya adalah URL ke lingkaran yang menjelaskan banyak hal.
reinierpost
4

Untuk beberapa tata bahasa, bukti dengan induksi (panjang kata lebih) dimungkinkan.


Pertimbangkan misalnya tata bahasa atas diberikan oleh aturan berikut:Σ = { a , b }GΣ={a,b}

SaSabSbε

Semua kata dengan panjang dalam - hanya ada - hanya memiliki satu derivasi-kiri.L ( G ) ε1L(G)ε

Asumsikan semua kata dengan panjang untuk beberapa hanya memiliki satu derivasi-kiri.nnN

Sekarang pertimbangkan sembarang untuk beberapa . Jelas, . Jika , kita tahu bahwa aturan pertama dalam setiap derivasi kiri harus ; jika , itu harus . Ini mencakup semua kasus. Dengan hipotesis induksi, kita tahu bahwa ada tepat satu derivasi kiri untuk . Dalam kombinasi, kami menyimpulkan bahwa ada tepat satu derivasi kiri untuk juga.w=w1wwnL(G)Σnn>0w1Σw1=aSaSaw1=bSbSbww


Ini menjadi lebih sulit jika

  • ada beberapa non-terminal,
  • tata bahasanya tidak linear, dan / atau
  • tata bahasanya adalah rekursif kiri.

Mungkin membantu memperkuat klaim terhadap semua bentuk sentensial (jika tata bahasa tidak memiliki terminal non-produktif) dan non-terminal "root".

Saya pikir konversi ke bentuk normal Greibach mempertahankan (tidak) ambiguitas, untuk menerapkan langkah ini terlebih dahulu dapat menangani rekursi kiri dengan baik.

Kuncinya adalah mengidentifikasi satu fitur dari setiap kata yang memperbaiki (setidaknya) satu langkah derivasi. Sisanya mengikuti secara induktif.

Raphael
sumber
3

Pada dasarnya, ini masalah generasi anak. Mulailah dengan ekspresi pertama, dan hasilkan anak-anak itu .... Terus lakukan itu secara rekursif (DFS), dan setelah beberapa iterasi, lihat apakah Anda dapat menghasilkan ekspresi diperluas yang sama dari dua anak yang berbeda. Jika Anda bisa melakukan itu, ini ambigu. Tidak ada cara untuk menentukan waktu berjalan dari algoritma ini. Anggap itu aman, setelah mungkin menghasilkan 30 level anak-anak :) (Tentu saja itu bisa meledak pada tanggal 31)

Karthik Kumar Viswanathan
sumber
1
OP meminta teknik pembuktian, bukan algoritma.
Raphael
2
itu tidak mungkin menjadi cara untuk membuktikan apakah tata bahasa ambigu atau tidak. Sebenarnya ketika pemboman itu terjadi tidak dapat dipastikan.
Sнаđошƒаӽ