Tentukan kesetaraan Nerode di atas bahasa sebagai iff untuk setiap .$L \subseteq \Sigma^{*}$$u \sim_L v$$uw \in L \Leftrightarrow vw \in L$$w \in \Sigma^{*}$

Nerode ekivalen memiliki banyak kelas ekivalensi tepat ketika dapat dikenali oleh otomat kondisi-terbatas. Ini adalah teorema Myhill-Nerode .${\sim}_L$$L$

Apakah ada karakterisasi serupa dari bahasa bebas konteks?

Motivasi:

Kelas ekivalen Nerode masing-masing sesuai dengan keadaan yang berbeda dalam setiap robot yang mengakui $L$ . Setiap CFL dapat dikenali oleh NPDA, yang memiliki sejumlah negara terbatas tetapi juga tumpukan simbol alfabet yang tidak terbatas. Stack melacak satu cara yang memungkinkan string dapat diurai. Jumlah kelas ekivalensi mungkin tak terbatas karena stack dapat menyimpan jumlah simbol yang tidak terbatas.

Saya bertanya: apakah selalu ada cara untuk menyatukan kelas kesetaraan sehingga setiap rumpun mewakili satu keadaan PDA, dengan masing-masing kelas dalam rumpun mewakili keadaan setara tumpukan untuk keadaan PDA itu?

Sebagai contoh, bahasa tanda kurung bersarang dengan benar hanya perlu negara untuk menangani popdan push, karena tumpukan akan melacak kedalaman bersarang saat ini. Jika penggumpalan seperti itu selalu dapat dilakukan, maka apakah jumlah rumpun itu terbatas menentukan apakah bahasa itu bebas konteks.

Seperti yang ditunjukkan oleh @sdcvvc dalam komentar, bentuk pertanyaan ini ditanyakan sebagai /math/118362 meskipun Yuval Filmus menjawab pertanyaan terkait pada Contoh bahasa bebas non-konteks yang tetap BISA dipompa? lebih relevan.

David S. Wise dalam makalahnya memberikan lemma pemompaan yang kuat untuk bahasa bebas konteks, sebuah lemma pemompaan yang kuat yang setara dengan bebas konteks. Dia juga menyediakan kondisi setara tambahan (properti 3 pada halaman 362) yang dia klaim dapat dilihat sebagai analog dari teorema Myhill-Nerode. Sebagai aplikasi yang terakhir, ia menunjukkan itu$\{ a^nba^{mn} : m,n > 0 \}$ tidak dapat diekspresikan sebagai persimpangan terbatas dari bahasa bebas konteks.

Informasi lebih lanjut tentang lemma pemompaan yang kuat muncul di salah satu jawaban saya .

Ada karakterisasi yang sangat bagus dari bahasa bebas konteks (dikreditkan ke Wechler) dalam makalah oleh Berstel dan Boasson, Menuju teori aljabar bahasa bebas konteks . Izinkan saya memperkenalkan beberapa definisi untuk menyatakan hasil ini (Teorema 3.1 di makalah).

The polinomial penutupan $Pol(\mathcal{L})$ sebuah kelas $\mathcal{L}$ bahasa dari $A^*$ adalah himpunan semua bahasa yang merupakan gabungan terbatas dari produk formulir $L_0a_1L_1 \dotsm a_nL_n$dimana $L_0, ..., L_n \in \mathcal{L}$ dan $a_1, ..., a_n \in A$.

Sebuah aljabar adalah kelas$\mathcal{A}$ bahasa yang mengandung bahasa tersebut $\{1\}$ dan seperti itu $\mathcal{A} = Pol(\mathcal{A})$. Ini dihasilkan secara halus jika$\mathcal{A} = Pol(\mathcal{F})$ untuk beberapa set yang terbatas $\mathcal{F}$bahasa. Itu stabil jika, untuk masing-masing$L \in \mathcal{A}$ dan $u \in A^*$, bahasa $u^{-1}L = \{v \mid uv \in L\}$ juga milik $\mathcal{A}$. Perhatikan bahwa itu sudah cukup untuk dimiliki$a^{-1}L \in \mathcal{A}$ untuk semua $a \in A$.

Teorema . Bahasa dari$A^*$ bebas konteks jika dan hanya jika itu milik aljabar stabil yang dihasilkan secara halus.

Lihat artikel untuk menerangi contoh dan banyak konsekuensi bagus.