Penutupan bahasa bebas konteks yang jelas di bawah pra dan postfix.

Himpunan $\mathit{ppc}(L)$ tentu saja bebas konteks, tapi saya pikir itu bisa secara inheren ambigu: pertimbangkan

L = {a^{m} b^{m} c^{n} d ∣ m, n \geq 0} \cup {d a^{m} b^{n} c^{n} ∣ m, n \geq 0},

$L=\{a^mb^mc^nd\mid m,n\geq 0\}\cup\{da^mb^nc^n\mid m,n\geq 0\}\;,$ lalu

p p c (L)

$\mathit{ppc}(L)$ termasuk bahasa klasik yang secara inheren ambigu

L^{'} = {a^{m} b^{m} c^{n} ∣ m, n \geq 0} \cup {a^{m} b^{n} c^{n} ∣ m, n \geq 0},

$L'=\{a^mb^mc^n\mid m,n\geq 0\}\cup\{a^mb^nc^n\mid m,n\geq 0\}\;,$ dan seseorang dapat membuktikan

p p c (L)

$\mathit{ppc}(L)$ juga secara inheren ambigu oleh argumen biasa (terapkan Ogden's Lemma pada

a^{n + n!} b^{n} c^{n}

$a^{n+n!}b^nc^n$ dan

a^{n} b^{n} c^{n + n!}

$a^nb^nc^{n+n!}$ untuk menyimpulkan keberadaan dua pohon yang berbeda untuk

a^{n + n!} b^{n + n!} c^{n + n!}

$a^{n+n!}b^{n+n!}c^{n+n!}$ ).

Sylvain
sumber

Terima kasih. Itu lebih mudah daripada saya. Apakah menurut Anda varian masalah (mis. Pre- dan postfix harus dibatasi (dengan simbol baru) menunjukkan hilangnya ketidak-ambiguan yang sama?

Martin Berger

Maksud Anda sesuatu seperti ? Kemudian mulai dari Anda akan menemukan bahwa memiliki dua pohon berbeda dalam tata bahasa untuk . Saya khawatir saya tidak tahu saat ini tentang bagaimana seseorang dapat memodifikasi (dengan cara sederhana) operasi untuk memastikan ketidakjelasan: awalan atau akhiran yang hilang dalam operasi mungkin penting untuk ketidakjelasan untuk memegang.

{p p c}_{$} (L) = {w $ ∣ \exists w^{'}, w w^{'} \in L} \cup {$ w ∣ \exists w^{'}, w^{'} w \in L}

$\mathit{ppc}_\$(L)=\{w\$\mid\exists w',\,ww'\in L\}\cup\{\$w\mid\exists w',\,w'w\in L\}$

L = {d a^{m} b^{m} c^{n} ∣ m, n \geq 0} \cup {e a^{m} b^{n} c^{n} ∣ m, n \geq 0}

$L=\{da^mb^mc^n\mid m,n\geq 0\}\cup\{ea^mb^nc^n\mid m,n\geq 0\}$

$ a^{n + n!} b^{n + n!} c^{n + n!}

$\$a^{n+n!}b^{n+n!}c^{n+n!}$

{p p c}_{$} (L)

$\mathit{ppc}_\$(L)$

p p c

$\mathit{ppc}$

Sylvain

Ya, sesuatu seperti itu. Karena ini tidak berhasil, saya harus mendesain ulang domain aplikasi saya. Terima kasih banyak atas masukan Anda.

Martin Berger

Penutupan bahasa bebas konteks yang jelas di bawah pra dan postfix.

Jawaban: