“Menanamkan” bahasa itu sendiri

Pertanyaan Utama / Umum

Biarkan menjadi bahasa. Tentukan bahasa dengan dan untuk . Pertimbangkan . Jadi, kami berulang kali "menyematkan" ke dalam dirinya sendiri untuk memperoleh . $L$ $L_i$ $L_0 = L$

L_{i} = {x w y : x y \in L_{i - 1}, w \in L}

$L_i = \{xwy : xy \in L_{i-1}, w \in L\}$

i \geq 1

$i \geq 1$

\hat{L} = ⋃ L_{i}

$\hat{L} = \bigcup L_i$

L

$L$

\hat{L}

$\hat{L}$

Sudahkah dipelajari? Apakah itu mempunyai nama? $\hat{L}$

Contoh / Motivasi

Seperti yang diminta di komentar oleh di sini adalah beberapa contoh untuk lebih menggambarkan apa itu. Maka karena tidak seorang pun (sejauh ini) tampaknya telah melihat gagasan ini, saya akan membahas motivasi saya untuk melihatnya. $\hat{L}$

Klaus Draeger mengalahkan saya untuk menambahkan contoh. Saya akan meletakkan contoh-contoh dari komentar di sini untuk meningkatkan visibilitas karena mereka adalah contoh yang baik.

Jika adalah bahasa yang unary , maka (dan karenanya teratur). $L$ $\hat{L} = L^+$

Jika , maka adalah bahasa Dyck . $L = {ab}$ $\hat{L}$

Berikut adalah cara alternatif untuk memikirkan . Diberi bahasa atas alfabet kami memainkan game berikut. Kami mengambil coba untuk mengurangi ke string kosong dengan berulang kali menghapus subwords yang berada di . (Di sini kita perlu sedikit berhati-hati bagaimana kita memperlakukan string kosong itu sendiri untuk memastikan bahwa ini setara dengan definisi di atas, tetapi ini secara moral benar.) $\hat{L}$ $L$ $A$ $w \in A^*$ $w$ $\epsilon$ $L$

Awalnya saya datang mendefinisikan dengan mempertimbangkan menghapus kekuatan dalam kata-kata. Ambil sebagai bahasa kubus di atas alfabet biner . Kemudian dan kita dapat mempertimbangkan " -deletion" berikut $\hat{L}$ $L = \{w^3 : w \in A^*\}$ $A = \{a,b\}$ $aaabaabaabbabab \in \hat{L}$ $L$

a (a a b a a b a a b) b a b a b \to a b a b a b \to ϵ .

$a(aabaabaab)babab \to ababab \to \epsilon.$

Amati tidak semua penghapusan akan berhasil

(a a a) b a a b a a b b a b a b \to b a a b a a b b a b a b

$(aaa)baabaabbabab \to baabaabbabab$

dan kita terjebak dengan kata bebas kubus. Jadi, ada notasi lain "sangat -deletable" yang secara umum tidak bertepatan dengan . $L$ $\hat{L}$

Satu contoh terakhir, jika dalam bahasa kuadrat di atas alfabet biner , maka adalah string dengan bilangan genap ' dan genap ' s. Jelas kondisi ini diperlukan. Salah satu cara untuk melihatnya cukup untuk mempertimbangkan menghapus kotak dan mengingat setiap kata biner dengan panjang 4 atau besar memiliki bujur sangkar. Di sini biasa. $L$ $A = \{a,b\}$ $\hat{L}$ $a$ $b$ $\hat{L}$

Untuk huruf yang lebih besar jenis argumen ini gagal karena ada kata-kata bebas persegi panjang sewenang - wenang . Dengan huruf berukuran saya dapat menunjukkan tidak biasa menggunakan Myhill-Nerode dan faktanya ada kata-kata bebas persegi panjang yang sewenang-wenang, tapi saya belum bisa mengatakan banyak lagi. Saya berharap melihatnya dengan cara yang lebih abstrak ini dapat menjelaskan situasi (dan definisi yang lebih abstrak ini tampaknya menarik dengan sendirinya). $k \geq 3$ $\hat{L}$

reference-request fl.formal-languages John Machacek
sumber

Bisakah Anda memberikan beberapa contoh ilustrasi?

phs

Beberapa contoh: jika adalah bahasa tunggal , maka adalah bahasa Dyck dari string kurung yang seimbang; untuk bahasa atas alfabet tunggal, kita dapat (jadi selalu teratur dalam kasus ini).

L

$L$

{()}

$\{()\}$

\hat{L}

$\hat{L}$

L = {a^{i} | i \in I}

$L=\{a^i|i\in I\}$

\hat{L} = L^{+}

$\hat{L}=L^+$

Klaus Draeger

@ phs Saya telah memodifikasi pertanyaan dengan (lebih banyak) lebih detail.

John Machacek

Satu hasil yang lebih relatif mudah adalah bahwa jika

adalah bebas konteks, kemudian jadi adalah

L

$L$

\hat{L}

$\hat{L}$

Klaus Draeger

Terima kasih atas contoh dan motivasi. Sekarang jauh lebih mudah untuk mengingat masalah Anda dan menyebarkannya. Terus perbarui pertanyaan awal Anda jika Anda memiliki perkembangan baru.

phs

Jawaban:

Pertanyaan ini terkait dengan apa yang disebut sistem penyisipan .

Sebuah sistem penyisipan adalah tipe khusus dari sistem yang aturan dari bentuk penulisan ulang untuk semua dalam diberikan bahasa . Mari kita menulis jika dan untuk beberapa . Mari kita tunjukkan dengan penutupan transitif refleksif dari relasi . Penutupan bahasa dari bawah $1 \rightarrow r$ $r$ $R$ $u \rightarrow_R v$ $u = u'u''$ $v = u'ru''$ $r \in R$ $\buildrel{*}\over\rightarrow_R$ $\rightarrow_R$ $L$ $A^*$ $\buildrel{*}\over\rightarrow_R$ adalah bahasa Ingat bahwa urutan kuasi yang baik pada set adalah relasi refleksif dan transitif sedemikian rupa sehingga untuk setiap urutan tak terbatas elemen , ada dua bilangan bulat sedemikian rupa sehingga . Teorema berikut ini dibuktikan dalam [1]:

[L]_{{\overset{*}{\to}}_{R}} = {v \in A^{*} ∣ there exists u \in L such that u {\overset{*}{\to}}_{R} v}

$[L]_{\buildrel{*}\over\rightarrow_R} = \{ v \in A^* \mid \text{ there exists $u \in L$ such that $u \buildrel{*}\over\rightarrow_R v$} \}$

E

$E$

⩽

$\leqslant$

x_{0}, x_{1}, \dots

$x_0, x_1, \ldots$

E

$E$

i < j

$i < j$

x_{i} ⩽ x_{j}

$x_i \leqslant x_j$

Jika adalah himpunan kata yang terbatas sehingga bahasa terbatas, maka hubungan adalah urutan quasi yang baik pada dan teratur. $H$ $A^* \setminus A^*HA^*$ $\buildrel{*}\over\rightarrow_R$ $A^*$ $[L]_{\buildrel{*}\over\rightarrow_R}$

[1] W. Bucher, A. Ehrenfeucht dan D. Haussler, Total regulator yang dihasilkan oleh hubungan derivasi, Theor. Komputasi. Sci. 40 , 2-3 (1985), 131-148.

J.-E. Pin
sumber

Sebagai J.-E. Pin menunjukkan penawaran pertanyaan saya dengan penyisipan . Saya telah menemukan sumber lain yang akan saya posting di sini untuk siapa pun yang tertarik.

L.Kari. Tentang Penyisipan dan Penghapusan dalam Bahasa Formal. Ph.D. Tesis, Universitas Turku, 1991.

Inilah Bagian I dan Bagian II dari tesis ini.

Dari apa yang saya tahu ini adalah sumber asli untuk studi penyisipan.

John Machacek
sumber