Properti penutupan non-CFL

Saya ditanyai oleh siswa berikut, dan tidak dapat memberikan jawaban lengkap:

Apakah ada properti penutupan untuk kelas bahasa yang tidak bebas konteks?

Cukup mudah untuk menemukan contoh yang menunjukkan bahwa itu tidak ditutup di bawah persimpangan dan iterasi (operator bintang Kleene), tetapi bagaimana dengan penyatuan dan penggabungan? Dugaan saya adalah bahwa itu tidak ditutup di bawah baik, jadi kecuali saya jauh, apa yang saya cari adalah contoh untuk dua non-CFL bahwa penyatuan atau penggabungan mereka adalah CFL.

fl.formal-languages context-free-languages Shir
sumber

Union memiliki contoh tandingan sepele karena ada bahasa yang tidak dapat ditentukan. Bahasa apa pun dengan pelengkapnya berfungsi.

Raphael

Murid-murid saya belum akrab dengan konsep keraguan.

Shir

Anda tidak perlu diputuskan, Anda hanya perlu bahwa bahasa maupun pelengkapnya bukan CFL.

Emil Jeřábek

Concatenation juga memiliki contoh tandingan sepele: ambil dua bahasa non-konteks bebas L1 dan L2 yang penyatuannya adalah Σ *, dan tambahkan string kosong ke L1 dan L2.

Tsuyoshi Ito

Persimpangan adalah mudah, mengambil dua bahasa memisah dari

, misalnya

dan

. Persatuan juga mudah, ambil dua bahasa yang persatuannya adalah

dan

\bar{C F L}

$\bar{CFL}$

{0 w : w \in L_{1}}

$\{0w : w \in L_1\}$

{1 w : w \in L_{1}}

$\{1w : w \in L_1\}$

Σ^{*}

$\Sigma^*$

{0 w : w \in L_{1}} \cup {1 w : w \in Σ^{*}}

$\{0w : w \in L_1\} \cup \{1w : w \in \Sigma^*\}$

{1 w : w \in L_{1}} \cup {0 w : w \in Σ^{*}}

$\{1w : w \in L_1\} \cup \{0w : w \in \Sigma^*\}$

Kaveh

Jawaban:

Mungkin ada sedikit atau tidak ada properti penutupan "menarik" dan "alami" untuk kelas bahasa yang tidak bebas konteks. Sebenarnya itu mungkin benar:

kelas bahasa apa pun yang ditentukan oleh robot, tata bahasa atau model komputasi tertentu - bahasa reguler, cfl, berbagai subkelas cfls seperti bahasa linier dan cfl deterministik, bahasa peka konteks, bahasa terbatas, dan begitu seterusnya.
Kelas sebenarnya didefinisikan oleh sifat penutupan, seperti keluarga setidaknya mengandung, katakanlah, { } dan ditutup di bawah operasi rutin dan transduksi. Sebenarnya, teori AFL adalah tentang hal-hal seperti itu. $a^n b^n$

Alasannya adalah bahwa banyak jika tidak semua atau semua properti penutupan "menarik" memiliki kemampuan untuk menyederhanakan bahasa secara drastis, misalnya memetakannya ke set terbatas atau sesuatu yang sama sederhana. Misalnya, Anda selalu dapat menerapkan homomorfisme konstan (h (a) = 0) ke bahasa bebas-konteks dan mendapatkan bahasa dari semua string nol, yang bebas konteks (sebenarnya reguler). Jadi, jika definisi dari kelas tersebut mensyaratkan bahwa itu tidak terlalu "sederhana" (seperti bebas-konteks-bebas), maka penutupan membawa Anda ke bahasa "sederhana", yaitu, di luar kelas.

Ini sebenarnya bisa membuat proyek penelitian yang menarik, yang bagiannya, saya akan menebak, akan mendefinisikan "sederhana", "menarik" dan "alami" dalam beberapa cara yang sesuai, dan juga untuk menemukan cara formal untuk berurusan dengan hal-hal sepele dan merosot kasus-kasus seperti yang saya berikan.

$\Sigma^*$

$a^*$

$\{a^{n-i}:i = \lfloor \sqrt n \rfloor\}$

$\{a^{n+i}:i = \lfloor \sqrt n \rfloor\}$

$\sqrt x$

David Lewis
sumber

Saya suka jawaban ini.

Suresh Venkat