Apakah set Sebelum dan Setelah untuk tata bahasa bebas konteks selalu bebas konteks?

Biarkan $G$ menjadi tata bahasa bebas konteks. Serangkaian terminal dan nonterminals dari $G$ dikatakan menjadi bentuk sentensial dari $G$ jika Anda bisa mendapatkannya dengan menerapkan produksi dari $G$ nol atau beberapa kali untuk simbol awal $S$ . Mari $\operatorname{SF}(G)$ adalah himpunan bentuk sentensial $G$ .

Mari $\alpha \in \operatorname{SF}(G)$ dan membiarkan $\beta$ menjadi substring dari $\alpha$ - kita sebut $\beta$ sebuah fragmen dari $\operatorname{SF}(G)$ . Sekarang mari

$\operatorname{Before}(\beta) = \{ \gamma \ |\ \exists \delta . \gamma \beta \delta \in \operatorname{SF}(G) \}$

dan

$\operatorname{After}(\beta) = \{ \delta \ |\ \exists \gamma . \gamma \beta \delta \in \operatorname{SF}(G) \}$ .

Apakah bahasa bebas konteks $\operatorname{Before}(\beta)$ dan $\operatorname{After}(\beta)$ ? Bagaimana jika $G$ tidak ambigu? Jika $G$ tidak ambigu, apakah $\operatorname{Before}(\beta)$ dan $\operatorname{After}(\beta)$ juga dijelaskan oleh bahasa bebas konteks yang tidak ambigu?

Ini adalah tindak lanjut dari pertanyaan saya sebelumnya , setelah upaya sebelumnya untuk membuat pertanyaan saya lebih mudah untuk dijawab gagal. Sebuah jawaban negatif akan membuat pertanyaan yang saya kerjakan sangat sulit dijawab.

Mari kita rasakan dulu dan setelah ( β ) . Pertimbangkan pohon derivasi yang mengandung β ; "mengandung" di sini berarti bahwa Anda dapat memotong sub pohon sehingga β adalah subword dari depan pohon. Kemudian, set sebelum (setelah) adalah semua bidang potensial dari bagian pohon kiri (kanan) dari β :$\operatorname{Before}(\beta)$$\operatorname{After}(\beta)$$\beta$$\beta$$\beta$

^{[ sumber ]}

Jadi kita harus membangun tata bahasa untuk bagian pohon yang berjejer secara horizontal. Tampaknya cukup mudah karena kita sudah memiliki tata bahasa untuk seluruh pohon; kita hanya perlu memastikan bahwa semua bentuk sentensial adalah kata-kata (ubah abjad), saring yang tidak mengandung (yang merupakan properti reguler karena β sudah diperbaiki) dan potong semua setelah (sebelum) β , termasuk β . Pemotongan ini juga harus dimungkinkan.$\beta$$\beta$$\beta$$\beta$

Sekarang menjadi bukti formal. Kami akan mengubah tata bahasa seperti diuraikan dan penggunaan penutupan sifat untuk melakukan penyaringan dan pemotongan, yaitu kita melakukan bukti non-konstruktif.$\mathrm{CFL}$

Biarkan tata bahasa bebas konteks. Sangat mudah untuk melihat bahwa SF ( G ) bebas konteks; membangun G ′ = ( N ′ , T ′ , δ ′ , N S ) seperti ini:$G = (N, T, \delta, S)$$\operatorname{SF}(G)$$G'=(N',T',\delta',N_S)$

• $N' = \{N_A \mid A \in N\}$
• $T' = N \cup T$
• $\delta' = \{\alpha(A) \to \alpha(\beta)\mid A\to\beta \in \delta \} \cup \{N_A \to A \mid A\in N\}$

dengan untuk semua t ∈ T dan α ( A ) = N A untuk semua a ∈ N . Jelas bahwa L ( G ′ ) = SF ( G ) ; oleh karena itu Pref penutupan closure yang sesuai ( SF ( G ) ) dan suffix closure suff ( SF ( G ) ) juga bebas konteks-.$\alpha(t)=t$$t \in T$$\alpha(A)=N_A$$a\in N$$\mathcal{L}(G')=\operatorname{SF}(G)$$\operatorname{Pref}(\operatorname{SF}(G))$$\operatorname{Suff}(\operatorname{SF}(G))$

Sekarang, untuk semua bahasa adalah L ( β ( N ∪ T ) ∗ ) dan L ( ( N ∪ T ) ∗ β ) . Seperti C F L ditutup di bawah persimpangan dan kanan / kiri quotient dengan bahasa biasa, kita mendapatkan$\beta \in (N\cup T)^*$$\mathcal{L}(\beta(N\cup T)^*)$$\mathcal{L}((N\cup T)^*\beta)$$\mathrm{CFL}$

$\qquad \displaystyle \operatorname{Before}(\beta) = (\operatorname{Pref}(\operatorname{SF}(G))\ \cap\ \mathcal{L}((N\cup T)^*\beta))\,/\,\beta \in \mathrm{CFL}$

dan

.$\qquad \displaystyle \operatorname{After}(\beta) = (\operatorname{Suff}(\operatorname{SF}(G))\ \cap\ \mathcal{L}(\beta(N\cup T)^*))\,\backslash\, \beta \in \mathrm{CFL}$

¹ adalah tertutup di bawah kanan (dan kiri) quotient ; Pref ( L ) = L / Σ * dan sama untuk Suff hasil awalan resp. penutupan akhiran.$\mathrm{CFL}$$\operatorname{Pref}(L) = L / \Sigma^*$$\operatorname{Suff}$

Ya, dan Setelah ( β ) adalah bahasa bebas konteks. Begini cara saya membuktikannya. Pertama, sebuah lemma (yang merupakan inti). Jika L adalah CF maka:$\mbox{Before}(\beta)$$\mbox{After}(\beta)$$L$

$\mbox{Before}(L,\beta) = \{ \gamma \ |\ \exists \delta . \gamma \beta \delta \in L \}$

dan

$\mbox{After}(L,\beta) = \{ \gamma \ |\ \exists \delta . \delta \beta \gamma \in L \}$

adalah CF.

Bukti? For membuat transduser T- β kondisi-terbatas non-deterministik yang memindai string, mengeluarkan setiap simbol input yang dilihatnya dan secara simultan mencari β secara deterministik . Setiap kali T β melihat simbol pertama β, ia bercabang secara non-deterministik dan berhenti menghasilkan simbol sampai ia selesai melihat β atau terlihat melihat simbol yang menyimpang dari β , berhenti pada kedua kasus. Jika T β melihat $\mbox{Before}(L,\beta)$$T_{\beta}$$\beta$$T_{\beta}$$\beta$$\beta$$\beta$$T_{\beta}$$\beta$secara penuh, ia menerima pada saat berhenti, yang merupakan satu-satunya cara ia menerimanya. Jika ia melihat penyimpangan dari , ia menolak.$\beta$

Lemma bisa disulap untuk menangani kasus-kasus di mana bisa tumpang tindih dengan dirinya sendiri (seperti sebuah b a b - terus mencari β bahkan saat di tengah-tengah scanning untuk sebelum β ) atau muncul beberapa kali (sebenarnya, asli non-determinisic forking sudah menangani itu). $\beta$$abab$$\beta$$\beta$

Sudah cukup jelas bahwa , dan karena CFL ditutup di bawah transduksi keadaan-terbatas, Before ( L , β ) adalah CF. $T_\beta(L) = \mbox{Before}(L,\beta)$$\mbox{Before}(L,\beta)$

Argumen serupa berlaku untuk , atau bisa juga dilakukan dengan pembalikan string dari Before ( L , β ) , CFL juga ditutup dengan pembalikan:$\mbox{After}(L,\beta)$$\mbox{Before}(L,\beta)$

$\mbox{After}(L,\beta) = \mbox{rev}(\mbox{Before}(\mbox{rev}(L),\mbox{rev}(\beta)))$

Sebenarnya, sekarang saya melihat argumen pembalikan, akan lebih mudah untuk memulai dengan , karena transduser untuk itu lebih mudah untuk dijelaskan dan diverifikasi - itu menghasilkan string kosong sambil mencari β . Ketika menemukan β itu bercabang non-deterministik, satu garpu terus mencari salinan lebih lanjut dari β , garpu lainnya menyalin semua karakter berikutnya secara verbatim dari input ke output, menerima semua sementara.$\mbox{After}(L,\beta)$$\beta$$\beta$$\beta$

Yang tersisa adalah membuat ini berfungsi untuk bentuk sentensial serta CFL. Tapi itu cukup mudah, karena bahasa bentuk sentimental CFG itu sendiri adalah CFL. Anda dapat menunjukkan bahwa dengan mengganti setiap non-terminal di seluruh G dengan mengatakan X ′ , menyatakan X sebagai terminal, dan menambahkan semua produksi X ′ → X ke tata bahasa.$X$$G$$X^\prime$$X$$X^\prime \rightarrow X$

Saya harus memikirkan pertanyaan Anda tentang ambiguitas.