Apakah ada analog "reguler" untuk string tak terbatas?

Pertimbangkan urutan . Tampaknya "biasa" dengan cara yang, misalnya tidak. $s_1 = (1, 0, 1, 0,\dots)$ $s_2 = (1, 2, 3, 4,\dots)$

Saya tidak yakin bagaimana memformalkan intuisi ini. Satu hal yang mengejutkan saya adalah bahwa adalah bahasa biasa, dan dalam batas tertentu adalah batasan dari string dalam bahasa ini. $L =\{(0 1)^n\}$ $s_1$

Apakah ada terminologi untuk mempertimbangkan string tanpa batas ini? Apakah kita memiliki sesuatu yang analog dengan lemma pemompaan, di mana kita dapat menyatakan bahwa string "infinite regular" semacam itu adalah dalam bentuk dengan , , hingga terbatas? $x y^ {\infty}z$ $x$ $y$ $z$

formal-languages regular-languages Xodarap
sumber

Mungkin periodik atau akhirnya periodik .

Yuval Filmus

Pumping : Pernyataan Anda tentang string tak terbatas bukanlah analog dari Pumping Lemma , yang mengatakan bahwa kata-kata yang cukup panjang dalam bahasa biasa mengandung substring yang dapat diulang untuk menghasilkan kata lain. Itu tidak mengatakan bahwa semua kata memiliki bentuk itu!

PJTraill

Terminologi : Anda berbicara tentang string yang teratur, sedangkan istilah biasa biasanya diterapkan ke bahasa.

PJTraill

Jawaban:

Mungkin istilah paling spesifik untuk menggambarkan string pertama Anda, $010101\dots$ adalah periodik . Sebuah benang $x_1x_2\dots$ (terbatas atau tak terbatas) adalah periodik jika ada $t$ sedemikian rupa, untuk semua $i$ , $x_i=x_{i+t}$ . Dalam hal contoh ini, kita dapat mengambil $t=2$ . Gagasan yang sedikit lebih lemah adalah bahwa string pada akhirnya periodik jika ada $n$ dan $t$ seperti yang $x_i=x_{i+t}$ untuk semua $i\geq n$ .

Lebih umum, meskipun, ada analog langsung dari bahasa reguler, yaitu $\omega$ - bahasa tidak teratur . Ini diakui oleh generalisasi alami automata terbatas. Set keadaan masih terbatas tetapi kriteria penerimaan harus dimodifikasi untuk berurusan dengan kata-kata yang tak terbatas - khususnya, kita tidak bisa hanya mengatakan "Terima jika robot selesai dalam keadaan menerima" karena robot tidak pernah selesai memproses inputnya yang tak terbatas.

Kelas automata paling sederhana untuk kata-kata tak terbatas adalah Büchi automata . Mereka didefinisikan persis seperti automata terbatas yang biasa Anda gunakan, dan mereka menerima input mereka jika setidaknya satu negara penerima sering dikunjungi tak terhingga selama menjalankan automaton. Satu perbedaan dari automata terbatas biasa adalah ternyata Büchi automata nondeterministik lebih kuat daripada deterministik, dan $\omega$ Bahasa tidak teratur adalah bahasa yang diterima oleh Büchi automata nondeterministic. Kriteria penerimaan masuk akal lainnya mengarah ke model otomat lain yang menerima kelas bahasa yang sama.

Perhatikan bahwa menulis itu tidak masuk akal $xy^\omega z$ , karena Anda tidak dapat memiliki apa pun setelah urutan tak terbatas $y$ s. Paling tidak, Anda tidak bisa jika posisi dalam string Anda diindeks oleh bilangan asli. Jika mereka diindeks oleh ordinan yang lebih besar, ini masuk akal.

Sebenarnya saya tidak ingat apakah ada analog dengan lemma pemompaan $\omega$ - bahasa tidak teratur. Ini sedikit memalukan, meskipun sudah satu dekade sejak saya mengajar kelas pascasarjana tentang hal ini.

David Richerby
sumber

Bagus. Mungkin menambahkan secara eksplisit itu

ω

$\omega$ -teraturan bahasa adalah gabungan bahasa yang terbatas

A B^{ω}

$AB^\omega$ dimana

A, B

$A,B$ reguler. Tidak tahu tentang memompa, tetapi kadang-kadang berguna untuk mengamati itu masing-masing

ω

$\omega$ -tertentu bahasa harus mengandung string akhirnya periodik.

Hendrik Jan

Saya selalu membenci presentasi standar lemma pemompaan karena begitu tumpul. Ketika Anda langsung ke sana, semua itu benar-benar mengatakan bahwa karena ada serangkaian negara terbatas, string apa pun dengan lebih banyak simbol daripada negara harus mengunjungi beberapa negara dua kali selama menjalankan otomat. Simbol yang berpartisipasi dalam lingkaran ini adalah simbol yang dapat Anda "pompa". Dipandang dari sudut ini, jelaslah bahwa ada analog ketika kita bertransisi ke string tanpa batas tetapi mempertahankan kondisi terbatas; jadi pertanyaannya bukan "apakah ada lemma yang memompa?" tetapi "seberapa rumitkah lemma pemompaan itu?".

Daniel Wagner

@DanielWagner: Wow, yeah ... presentasi standar memang cukup bodoh dan milik Anda membuatnya jelas. Terima kasih atas penjelasannya!

user541686

@DanielWagner: lemma pemompaan tentu membingungkan, tetapi keuntungan dari presentasi standar adalah bahwa itu tidak merujuk pada mekanisme automata, ekspresi reguler, atau cara khusus lainnya dalam mendefinisikan bahasa reguler. Itu hanya berbicara tentang string!

Max

@ Max Keuntungan yang meragukan memang!

Daniel Wagner

Ini adalah hasil dasar dalam Tipe Dua Efektivitas, yang saya pikir menjawab pertanyaan Anda dari sudut pandang yang dapat dihitung. Berikut ini, bahasa kami hanya terdiri dari string tak terbatas. Kami menunjukkan serangkaian string tak terbatas $\Sigma^\omega$ .

Teorema: Jika sebuah automaton yang dapat direalisasikan berakhir pada setiap string tanpa batas, maka bahasa dari automaton sama dengan $S\Sigma^\omega$ dimana $S$ adalah seperangkat string terbatas.

The Buktinya adalah dengan lemma Konig ini.

Kesimpulannya adalah bahwa bahasa lebih dari string tak terbatas entah "sederhana" dalam arti tertentu (yang merupakan fakta menarik ) atau tidak dapat diputuskan. Gagasan non-sepele tentang bahasa di atas string tanpa batas tidak dapat ditentukan.

Anda mungkin bisa belajar bahasa kurang sederhana jika Anda mengizinkan keanggotaan untuk menjadi semidecidable daripada decidable. Ini masih dapat dianggap sebagai "ilmu komputer" dan bukan hanya matematika infinitari (ini berkaitan dengan masalah pencarian alih-alih masalah keputusan; kesanggupan dalam hal tertentu cukup memadai untuk melakukan pencarian).

ogogmad
sumber