Apakah dapat memutuskan apakah bahasa yang dijelaskan dengan jumlah kejadian teratur?

Diberi dua kata , , apakah bisa diputuskan jika bahasa dari kata-kata yang mengandung jumlah yang sama dari dan adalah reguler? $w_1$ $w_2$ $L$ $w_1$ $w_2$

Pertama, beberapa definisi:
Mereka dapat dibuat lebih ringkas, dan notasi dapat ditingkatkan jika mereka akan digunakan dalam bukti. Ini hanya konsep pertama.

Diberi dua kata dan , kita mengatakan bahwa: $w_1$ $w_2$

selalu terjadidengan , catat , iff $w_1$ $w_2$ $w_1\triangleleft w_2$
1. untuk setiap string sehingga dengan $s$ $s=xw_2y$ dan ada dekomposisi lain . Catatan: Kondisi yang dan $\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid w_2\mid$ $|x|_0,|x|_1|,|y|_0,|y|_1| \geq 1$ $s=x'w_1y'$
  $x$ $y$ masing-masing mengandung setidaknya 0 dan 1 diperlukan oleh kasus patologis (ditemukan oleh @ sdcvvc): , dan , dan varian simetrisnya. $w_1=1^i0$ $w_2=v1^{i+j}$ $y\in1^*$
2. ada string dengan $s=xw_2y$ sedemikian rupa sehingga ada paling banyak satu dekomposisi $\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid w_2\mid$ $s=x'w_1y'$
selalu berdampingandengan , catat $w_1$ $w_2$ , jika masing-masing selalu terjadi dengan yang lain, $w_1\triangleleft \triangleright\,w_2$
dan muncul secara independen, catat $w_1$ $w_2$ , jika tidak ada yang selalu terjadi dengan yang lain, $w_1\triangleright \triangleleft\,w_2$
selalu terjadi kali atau lebihdari , mencatat , IFF untuk string sehingga dengan ada dekomposisi lainnya $w_1$ $m$ $w_2$ $w_1\triangleleft_m w_2$ $s$ $s=xw_2y$ $\mid x\mid,\ \mid y\mid|\ \geq \mid w_1\mid +\mid w_2\mid$ $m$ $s=x_iw_1y_i$ untuk sehingga menyiratkan . $i\in[1,m]$ $i\neq j$ $x_i\neq x_j$

Definisi-definisi ini dikonstruksi sedemikian sehingga kita dapat mengabaikan apa yang terjadi di ujung string di mana dan seharusnya terjadi. Efek batas pada akhir string harus dianalisis secara terpisah, tetapi mereka mewakili sejumlah kasus yang terbatas (sebenarnya saya pikir saya lupa satu atau dua sub-kasus batas seperti itu dalam analisis pertama saya di bawah, tetapi tidak terlalu penting). Definisi tersebut kompatibel dengan tumpang tindih kejadian. $w_1$ $w_2$

Ada 4 kasus utama untuk dipertimbangkan (mengabaikan simetri antara dan ): $w_1$ $w_2$

Kedua kata datang tentu bersama-sama, kecuali mungkin di ujung tali. Ini hanya menyangkut pasangan formulir dan , atau dan . Ini mudah dikenali olehotomat terbatasyang hanya memeriksa kejadian tunggal di kedua ujung tali untuk dikenali, untuk memastikan ada satu-satunya kejadian di kedua ujung atau di kedua ujung. Ada juga kasus merosot ketika : maka bahasa L jelas teratur. $w_1\triangleleft \triangleright\,w_2$
$1^i0$ $01^i$ $0^i1$ $10^i$ $w_1=w_2$
, tetapi tidak Salah satu dari 2 kata tidak dapat muncul tanpa yang lain, tetapi kebalikannya tidak benar (kecuali mungkin di ujung string). Ini terjadi ketika: $w_1\triangleleft w_2$ $w_2\triangleleft w_1$
- adalah substring dari : maka otomat terbatas hanya dapat memeriksa bahwa tidak terjadi di luar instance dari . $w_1$ $w_2$ $w_1$ $w_2$
- dan untuk beberapa kata , : lalu cek otomat terbatas seperti dalam kasus sebelumnya bahwa tidak terjadi terpisah dari . Namun, otomat memungkinkan menghitung satu contoh ekstra dari yang akan memungkinkan penerimaan jika $w_1=1^i0$ $w_2=v1^j$ $v\in\{0,1\}^*$ $v\neq01^i$ $w_1$ $w_2$ $w_1$ $w_2$ adalah akhiran dari string. Ada tiga kasus simetris lainnya (simetri 1-0 dan simetri kanan-kiri).
Salah satu dari 2 kata tersebut muncul dua kali di yang lain. Itu dapat dikenali oleh otomatisasi terbatas yang memeriksa bahwa kata yang lebih kecil tidak pernah muncul dalam string. Varian ini juga merupakan varian yang sedikit lebih kompleks yang menggabungkan dua variasi case 2. Dalam hal ini automaton memeriksa bahwa string yang lebih kecil tidak pernah terjadi, kecuali mungkin sebagai bagian dari dalam yang lebih besar datang sebagai suffix string (dan 3 kasus lainnya dengan simetri). $w_1\triangleleft_2 w_2$
$1^i0$ $v$ $v1^j$
Kata-kata itu dapat terjadi secara independen satu sama lain. Kami membangun -mesin umum-sekuensial (gsm)yang menghasilkan ketika ia mengakui terjadinya dan ketika mengenali kejadian , dan melupakan yang lainnya. Bahasa hanya reguler jika bahasa teratur. Tapi $w_1\triangleright \triangleleft\,w_2$
$G$ $a$ $w_1$ $b$ $w_2$ $L$ $G(L)$ yang jelas bebas konteks dan tidak teratur. Karenanya tidak teratur. Sebenarnya kami memiliki . Karena bahasa reguler dan bahasa bebas konteks ditutup di bawah pemetaan gsm dan pemetaan gsm terbalik, kami juga tahu bahwa bebas dari konteks. $G(L)=\{w\in\{a,b\}^*\mid\ \mid w\mid_a=\mid w\mid_b\}$ $L$
$L=G^{-1}(G(L))$ $L$

Salah satu cara untuk mengatur bukti formal adalah sebagai berikut. Pertama-tama buatlah PDA yang mengenali bahasa itu. Sebenarnya itu dapat dilakukan dengan mesin 1-counter, tetapi lebih mudah untuk memiliki dua simbol stack untuk menghindari duplikasi kontrol yang terbatas. Kemudian, untuk kasus di mana seharusnya FA, tunjukkan bahwa penghitung dapat dibatasi oleh konstanta yang hanya bergantung pada dua kata. Untuk kasus lain, tunjukkan bahwa penghitung dapat mencapai nilai arbitrer apa pun. Tentu saja, PDA harus diatur sehingga buktinya cukup mudah untuk dibawa.

Mewakili FA sebagai 2-stack-symbol PDA mungkin adalah representasi paling sederhana untuk itu. Dalam kasus non-reguler, bagian kendali terbatas dari PDA adalah sama dengan GSM dalam sketsa bukti di atas. Alih-alih mengeluarkan dan seperti GSM, PDA menghitung perbedaan jumlah dengan stack. $a$ $b$

babou
sumber

Saya punya pertanyaan tentang kehebatan konteks dalam kasus tiga kata. Saya menghapusnya ketika saya menyadari itu bisa dianalisis dengan cara yang sama. Saya pertama kali berpikir bahwa membuktikan non-CFness akan membuat latihan orisinal, tetapi GSM merusaknya.

babou

Tidak jelas apa yang Anda maksud dengan "terjadi secara independen satu sama lain", "datang bersama-sama" dll. Silakan tulis definisi formal sebagai gantinya, dan buktikan bahwa mereka mencakup semua kasus.

sdcvvc

Saya tidak yakin apa yang Anda minta, dan tingkat formalisasi apa yang Anda butuhkan, untuk tujuan apa. Saya menyadari bahwa menganalisis dengan tangan kemungkinan hubungan kedua kata tersebut tidak dijamin benar, dan bagaimanapun juga tidak masalah. Yang penting adalah apakah kemunculan satu kata dapat ada tanpa menciptakan pada saat yang sama suatu kemunculan (atau beberapa) kata lain. Detailnya tidak masalah karena akan selalu dilokalkan dan dengan demikian dapat dikelola dengan baik. Kedua ujungnya tidak menjadi masalah karena juga terlokalisir. Bahkan tumpang tindih kejadian tidak masalah karena mereka hanya bisa banyak di 1 tempat

babou

Saya bertanya tentang definisi yang tepat dari istilah yang disebutkan dalam komentar. Terima kasih telah menulisnya. Apakah saya seharusnya menebak mereka sebelumnya? Bagaimanapun, Anda tampaknya mengklaim bahwa

. Ini tidak memenuhi kondisi 1. definisi "

selalu terjadi dengan

", karena tidak ada terjadinya

0^{i} 1 ◃ ▹ 1 0^{i}

$0^i 1 \triangleleft \triangleright 1 0^i$

w_{1}

$w_1$

w_{2}

$w_2$

1 0^{i}

$1 0^i$

s = 0^{M} 0^{i} 1 1^{M}

$s=0^M 0^i 1 1^M$

sdcvvc

Maaf, saya tidak bermaksud membuat Anda menebak. Hanya butuh waktu bagi saya untuk memahami apa yang sebenarnya Anda inginkan. Hanya gagal saya. Mengenai contoh balasan Anda, Anda benar. Tetapi bagi saya itu hanya berarti bahwa saya harus sedikit lebih berhati-hati tentang telomer, dalam definisi hubungan. Saya mendefinisikannya terlalu cepat, tetapi

atau

tidak menyampaikan banyak informasi dalam konteks ini. Ini benar-benar contoh patologis batas dalam kasus patologis, yang sebenarnya tidak dapat terjadi ketika lebih dari 2 simbol digunakan. Saya hanya tidak percaya itu mengubah apa pun.

0^{M}

$0^M$

1^{M}

$1^M$

babou

Apakah dapat memutuskan apakah bahasa yang dijelaskan dengan jumlah kejadian teratur?

Jawaban: