Apa set panjang kata yang mungkin dalam bahasa biasa?

Diberi bahasa , tentukan panjang himpunan L sebagai himpunan panjang kata dalam L : L S ( L ) = { | kamu | ∣ u ∈ L $L$$L$$L$

Set bilangan bulat mana yang dapat menjadi set panjang bahasa reguler?

Pertama, pengamatan yang tidak penting tetapi nyaman: himpunan $\mathscr{S}$ himpunan bilangan bulat yang merupakan $LS(L)$ untuk beberapa bahasa reguler $L$ pada alfabet non-kosong $\mathscr{A}$ tidak bergantung pada pilihan alfabet. Untuk melihat itu, pertimbangkan otomat terbatas yang mengenali $L$ ; panjang kata-kata yang ada di $L$ adalah panjang jalur pada otomat yang dilihat sebagai grafik yang tidak berlabel dari keadaan mulai ke keadaan terima apa pun. Secara khusus, Anda dapat menandai ulang setiap panah ke $a$ dan mendapatkan bahasa reguler dengan panjang yang sama yang ditetapkan pada alfabet $\{a\}$ . Sebaliknya, jika$L$ adalah bahasa biasa di atas alfabet satu elemen, itu bisa disuntikkan ke dalam alfabet yang lebih kecil, dan hasilnya masih bahasa biasa.

Oleh karena itu kami mencari set panjang kata yang mungkin untuk alfabet tunggal. Pada alfabet tunggal, bahasa adalah panjang yang ditetapkan ditulis dalam unary: $\mathrm{LS}(L) = \{n\in\mathbb{N} \mid a^n \in L\}$ . Bahasa seperti itu disebut bahasa unary.

Biarkan $L$ menjadi bahasa biasa, dan mempertimbangkan robot yang terbatas deterministik (DFA) yang mengakui $L$ . Himpunan panjang kata-kata $L$ adalah himpunan panjang lintasan dalam DFA yang dilihat sebagai grafik berarah yang dimulai pada keadaan awal dan berakhir di salah satu negara terima. DFA pada alfabet satu elemen cukup jinak (NFA akan lebih liar): itu adalah daftar terbatas atau daftar bundar. Jika daftar terbatas, beri nomor status dari $0$ hingga $h$ mengikuti urutan daftar; jika melingkar, beri nomor negara dari $0$ sampai $h$ mengikuti kepala daftar, dan $h$ ke $h+r$ sepanjang loop.

Misalkan $F$ adalah himpunan indeks keadaan terima hingga $h$ , dan $G$ adalah himpunan indeks keadaan terima dari $h$ ke $h+r$ . Kemudian

Sebaliknya, misalkan $h$ dan $r$ menjadi dua bilangan bulat dan $F$ dan $G$ menjadi dua set bilangan bulat yang terbatas sehingga $\forall x \in F, x \le h$ dan$\forall x \in G, h \le x \le h+r$ . Kemudian set$L_{F,G,r} = \{ a^{k\,r+x} \mid x\in G, k\in\mathbb{N} \}$adalah bahasa biasa: itu adalah bahasa yang dikenali oleh DFA yang dijelaskan di atas. Sebuah ekspresi reguler yang menjelaskan bahasa ini adalah$a^F \mid a^{G} (a^r)^*$ .

Untuk meringkas dalam bahasa Inggris, set panjang bahasa reguler adalah set integer yang periodik¹ di atas nilai tertentu .

¹ _{Untuk berpegang pada gagasan yang mapan , periodik berarti fungsi karakteristik set (yang merupakan fungsi $\mathbb{N}\to\{\mathtt{false},\mathtt{true}\}$ yang kita angkat ke fungsi$\mathbb{Z}\to\{\mathtt{false},\mathtt{true}\}$ ) periodik. Berkala di atas nilai tertentu berarti bahwa fungsi yang dibatasi pada$[h,+\infty[$ dapat diperpanjang menjadi fungsi periodik.}

Setiap himpunan bagian terbatas dapat menjadi lenght-set bahasa L biasa , karena Anda dapat mengambil alfabet unary { 0 } dan mendefinisikan L sebagai $\{\ell_1,\ldots,\ell_n\}\subset\mathbb{N}$$L$$\{0\}$$L$ (ini termasuk bahasa kosong dan { ε } ).$\{0^{\ell_1},\ldots,0^{\ell_n}\}$$\{\varepsilon\}$

Sekarang untuk set yang tak terbatas. Saya akan memberikan analisis singkat, meskipun jawaban akhirnya mungkin tidak cukup eksplisit. Saya tidak akan menguraikan kecuali Anda meminta saya untuk, karena saya pikir itu intuitif dan karena saya tidak punya banyak waktu sekarang.

Mari menjadi ekspresi reguler yang menghasilkan bahasa L 1 dan L 2 , masing-masing. Sangat mudah untuk melihatnya$r_1,r_2$$L_1$$L_2$

• .$\mathsf{LS}(L(r_1+r_2))=\mathsf{LS}(L_1\cup L_2)=\mathsf{LS}(L_1)\cup\mathsf{LS}(L_2)$
• . Ini dilambangkan L S ( L 1 ) + L S ( $\mathsf{LS}(L(r_1r_2))=\mathsf{LS}(L_1L_2)=\{\ell_1+\ell_2:\ell_1\in\mathsf{LS}(L_1),\ell_2\in\mathsf{LS}(L_2)\}$ .$\mathsf{LS}(L_1)+\mathsf{LS}(L_2)$
• $$\mathsf{LS}(L(r_1^*))=\{0\}\cup\bigcup_{n\geq 1}\Big\{\sum_{i=1}^n\ell_i:(\ell_1,\ldots,\ell_n)\in\big(\mathsf{LS}(L_1)\big)^n\Big\}.$$

Dengan demikian, himpunan bilangan bulat yang mungkin dapat menjadi himpunan-panjang dari bahasa reguler adalah yang merupakan himpunan himpunan terbatas atau yang dapat dibangun dengan mengambil himpunan himpunan terbatas S 1 , S 2 dari $\mathbb{N}$$S_1,S_2$$\mathbb{N}$ dan menggunakan rumus-rumus sebelumnya hingga. berkali-kali.

Di sini, kami menggunakan bahasa reguler yang dibangun, menurut definisi, dengan menerapkan aturan untuk membangun ekspresi reguler beberapa kali. Perhatikan bahwa kita dapat mulai dengan subset terbatas hingga , meskipun dalam ekspresi reguler kita mulai dengan kata-kata dengan panjang 0 dan 1 hanya sebagai basis huruf. Ini mudah dibenarkan oleh fakta bahwa semua kata (terbatas) adalah gabungan dari simbol alfabet.$\mathbb{N}$

Menurut lemma pemompaan untuk bahasa reguler, ada sehingga string x dengan panjang setidaknya sama dengan n dapat ditulis dalam bentuk berikut: x = u v w Dimana tiga kondisi berikut berlaku: | kamu v | < n | v | > 0 u v k w ∈ $n$$x$$n$

Ini memberi kita satu pengujian untuk set: suatu set tidak dapat menjadi set panjang dari bahasa reguler kecuali semua elemennya dapat dinyatakan sebagai beberapa set integer acak tidak lebih dari tetap , ditambah beberapa kelipatan dari nilai yang tidak ditentukan m (panjang dari $n$$m$$v$ ), ditambah beberapa nilai terbatas yang berubah-ubah.

Dengan kata lain, sepertinya set panjang bahasa yang mungkin untuk bahasa reguler adalah penutupan sehubungan dengan set union (seperti yang dibahas di bawah EDIT dan EDIT2, terima kasih kepada komentator) dari set yang dijelaskan sebagai berikut: Untuk memperbaiki a , b ∈ N dan semua himpunan terbatas S , oleh lemma pemompaan untuk bahasa reguler (terima kasih kepada Gilles karena menunjukkan kesalahan konyol dalam versi asli saya, di mana saya mendefinisikan set

EDIT: Sedikit diskusi lagi. Tentu saja semua himpunan bilangan bulat terbatas adalah himpunan panjang. Juga, penyatuan dua himpunan panjang juga harus merupakan himpunan panjang, sebagaimana harus menjadi pelengkap dari himpunan panjang apa pun (karenanya persimpangan, maka perbedaan). Alasan untuk ini adalah bahwa bahasa reguler ditutup di bawah operasi ini. Oleh karena itu, jawaban yang saya berikan di atas (mungkin) tidak lengkap; pada kenyataannya, setiap penyatuan dari set tersebut juga merupakan set panjang dari beberapa bahasa reguler (perhatikan bahwa saya telah meninggalkan yang membutuhkan persimpangan, komplemen, perbedaan, dll., karena ini tercakup oleh fakta bahwa bahasa biasa ditutup di bawah properti ini, seperti dibahas dalam EDIT3; Saya pikir hanya persatuan yang benar-benar diperlukan, bahkan jika yang lain benar, yang mungkin tidak demikian).

EDIT2: Diskusi lebih lanjut. Jawaban yang saya berikan pada dasarnya adalah di mana Anda akan berakhir jika Anda mengambil jawaban Janoma sedikit lebih jauh; itu$bn$$a$ berasal dari gabungan, dan pembahasan union, intersection, perbedaan dan komplemen berasal dari + ekspresi reguler (serta sifat penutupan lain dari bahasa biasa) dapat dibuktikan mulai dari automata) .

EDIT3: Sehubungan dengan komentar Janoma, mari kita lupakan sifat penutupan set panjang bahasa yang saya bahas dalam EDIT pertama. Karena bahasa reguler memiliki properti penutup ini, dan karena setiap bahasa reguler memiliki DFA, maka bahasa yang digunakan untuk bahasa biasa berlaku untuk semua serikat pekerja, persimpangan, pelengkap, dan perbedaan bahasa biasa, dan kami akan membiarkannya begitu saja ; bahkan tidak perlu mempertimbangkan semua ini, kecuali penyatuan, yang menurut saya masih perlu untuk membuat yang asli (dimodifikasi, terima kasih atas masukan dari Gilles) yang benar. Jadi, jawaban terakhir saya adalah ini: apa yang saya katakan di versi asli, ditambah penutupan set panjang bahasa sehubungan dengan set union.