Tentukan kelas bahasa "sirkular" berikut di atas alfabet alfabet hingga. Sebenarnya, nama itu sudah ada untuk menunjukkan hal yang berbeda tampaknya, digunakan di bidang komputasi DNA. AFAICT, itu kelas bahasa yang berbeda.
Bahasa L adalah bundaran iff untuk semua kata di , kami memiliki:
milik L jika dan hanya jika untuk semua bilangan bulat , milik L.
Apakah kelas bahasa ini dikenal? Saya tertarik pada bahasa sirkuler yang juga teratur dan khususnya dalam:
nama untuk mereka, jika mereka sudah dikenal
decidability masalah, diberikan otomat (khususnya: DFA), apakah bahasa yang diterima mematuhi definisi di atas
fl.formal-languages
automata-theory
regular-language
vincenzoml
sumber
sumber
Jawaban:
Pada bagian pertama, kami menunjukkan algoritma eksponensial untuk menentukan sirkularitas. Pada bagian kedua, kami menunjukkan bahwa masalahnya adalah coNP-hard. Pada bagian ketiga, kami menunjukkan bahwa setiap bahasa melingkar adalah penyatuan bahasa bentuk (di sini rr+ r bisa menjadi regexp kosong); serikat tidak harus terputus-putus. Pada bagian keempat, kami menunjukkan bahasa melingkar yang tidak dapat ditulis sebagai jumlah terpisah .∑r+i
Sunting: Menyertakan beberapa koreksi mengikuti komentar Mark. Secara khusus, klaim saya sebelumnya bahwa edaran telah lengkap atau NP-keras diperbaiki.
Sunting: Bentuk normal yang dikoreksi dari ke ∑ r + i . Memperlihatkan bahasa "inheren ambigu".∑r∗i ∑r+i
Melanjutkan komentar Peter Taylor, berikut ini cara memutuskan (sangat tidak efisien) apakah suatu bahasa melingkar mengingat DFA-nya. Bangun DFA baru yang negaranya adalah -tupel dari state lama. DFA baru ini menjalankan n salinan DFA lama secara paralel.n n
Jika bahasa tidak melingkar maka ada kata sehingga jika kita menjalankannya melalui DFA berulang kali, dimulai dengan keadaan awal s 0 , maka kita mendapatkan status s 1 , ... , s n sehingga s 1 menerima tetapi satu dari yang lain tidak menerima (jika semua dari mereka yang menerima maka maka urutan s 0 , ... , s n keharusan siklus sehingga w * selalu dalam bahasa). Dengan kata lain, kita memiliki jalur dari s 0 , ... , s nw s0 s1,…,sn s1 s0,…,sn w∗ ke s 1 ,…, s n di mana s 1 menerima tetapi yang lain tidak menerima. Sebaliknya, jika bahasanya melingkar maka itu tidak bisa terjadi.s0,…,sn−1 s1,…,sn s1
Jadi kami telah mengurangi masalah menjadi tes keterjangkauan yang diarahkan sederhana (cukup periksa semua kemungkinan "buruk" -tupel).n
Masalah sirkularitas adalah coNP-keras. Misalkan kita diberi contoh 3SAT dengan variabel → x dan m klausa C 1 , ... , C m . Kita dapat mengasumsikan bahwa n = m (tambahkan variabel dummy) dan n itun x⃗ m C1,…,Cm n=m n adalah bilangan prima (jika tidak temukan bilangan prima antara dan 2 n menggunakan pengujian primitif AKS, dan tambahkan variabel dummy dan klausa).n 2n
Pertimbangkan bahasa berikut: "input bukan dari bentuk mana → x i adalah tugas yang memuaskan untuk C i ". Mudah untuk membuat DFA O ( n 2 ) untuk bahasa ini. Jika bahasa tidak melingkar maka ada kata w dalam bahasa, beberapa kekuatan yang tidak ada dalam bahasa. Karena satu-satunya kata yang tidak dalam bahasa memiliki panjang n 2 , w harus dengan panjang 1 atau n . Jika panjangnyax⃗ 1⋯x⃗ n x⃗ i Ci O(n2) w n2 w 1 n , pertimbangkan w n1 wn sebagai gantinya (masih dalam bahasa), sehingga adalah dalam bahasa dan w n tidak dalam bahasa. Fakta bahwa w n tidak dalam bahasa berarti bahwa w adalah tugas yang memuaskan.w wn wn w
Sebaliknya, setiap tugas memuaskan diterjemahkan ke kata membuktikan non-bundar dari bahasa: memuaskan tugas milik bahasa tetapi w n tidak. Jadi bahasanya melingkar jika instance 3SAT tidak memuaskan.w wn
Pada bagian ini, kita membahas bentuk normal untuk bahasa sirkuler. Mempertimbangkan beberapa DFA untuk bahasa melingkar . Urutan C = C 0 , ... adalah nyata jika C 0 = s (keadaan awal), semua negara lainnya menerima, dan C i = C j menyiratkan C i + 1L C=C0,… C0=s Ci=Cj . Dengan demikian setiap urutan nyata pada akhirnya bersifat periodik, dan hanya ada banyak urutan nyata (karena DFA memiliki banyak negara).Ci+1=Cj+1
Kami mengatakan bahwa kata berperilaku sesuai denganC jika kata mengambil DFA dari negara untuk negara c i + 1 , untuk semua i . Himpunan semua kata seperti itu E ( C ) teratur (argumennya mirip dengan bagian pertama dari jawaban ini). Perhatikan bahwa E ( C ) adalah bagian dari L .ci ci+1 i E(C) E(C) L
Mengingat nyata urutan , mendefinisikan C k menjadi urutan C k ( t ) = C ( k t ) . Urutan C k juga nyata. Karena hanya ada finitely banyak urutan yang berbeda C k , bahasa D ( C ) yang merupakan gabungan dari semua E ( C k ) juga biasa.C Ck Ck(t)=C(kt) Ck Ck D(C) E(Ck)
Kami mengklaim bahwa memiliki sifat bahwa jika x , y ∈ D ( C ) maka x y ∈ D ( C ) . Memang, anggaplah bahwa x ∈ C k dan y ∈ C l . Kemudian x y ∈ C k + l . Jadi D ( C ) = DD(C) x,y∈D(C) xy∈D(C) x∈Ck y∈Cl xy∈Ck+l dapat ditulis dalam bentuk rD(C)=D(C)+ untuk beberapa ekspresi reguler r .r+ r
Setiap kata dalam bahasa sesuai dengan beberapa urutan C nyata , yaitu ada urutan C nyata yang sesuai dengan w . Jadi L adalah gabungan dari D ( C ) atas semua urut nyata C . Oleh karena itu setiap bahasa sirkuler memiliki representasi bentuk ∑ r +w C C w L D(C) C . Sebaliknya, setiap bahasa seperti itu melingkar (sepele).∑r+i
Pertimbangkan bahasa sirkular dari semua kata di atas a , b yang mengandung angka genap atau a atau bilangan genap b (atau keduanya). Kami menunjukkan bahwa itu tidak dapat ditulis sebagai jumlah yang terpisah ∑ r + i ; oleh "disjoint" yang kami maksud adalah r + i ∩ r + j = ∅ .L a,b a b ∑r+i r+i∩r+j=∅
Biarkan menjadi ukuran beberapa DFA untuk r + i , dan N > maks N i menjadi bilangan bulat ganjil . Pertimbangkan x = a N b N ! . Karena x ∈ L , x ∈ r + i untuk beberapa i . Oleh lemma memompa, kita dapat memompa awalan dari x panjang paling N . Jadi r + i menghasilkan z = a N !Ni r+i N>maxNi x=aNbN! x∈L x∈r+i i x N r+i . Demikian pula, ∉ L . Dengan demikian representasi tidak dapat dipisahkan.z=aN!bN! dihasilkan oleh beberapa r + j , yang juga menghasilkan z . Perhatikan bahwa saya ≠ j sejak x yy=aN!bN r+j z i≠j xy∉L
sumber
Berikut adalah beberapa makalah yang membahas bahasa-bahasa ini:
Thierry Cachat, Kekuatan bahasa rasional satu huruf, DLT 2001, Springer LNCS # 2295 (2002), 145-154.
S. Hovath, P. Leupold, dan G. Lischke, Akar dan kekuatan bahasa reguler, DLT 2002, Springer LNCS # 2450 (2003), 220-230.
H. Bordihn, Keanggunan konteks dari kekuatan bahasa bebas konteks tidak dapat diputuskan, TCS 314 (2004), 445-449.
sumber
@Dave Clarke, L = a * | b * akan melingkar, tetapi L * akan menjadi (a | b) *.
Dalam hal decidability, bahasa melingkar jika ada L ′ sehingga L adalah penutupan di bawah + dari L ′L L′ L L′ atau jika itu adalah gabungan terbatas dari bahasa melingkar.
(Saya ingin mendefinisikan "sirkular" menggantikan Anda dengan ≥ . Ini sangat menyederhanakan banyak hal. Kita kemudian dapat mengkarakterisasi bahasa sirkuler sebagai bahasa yang terdapat NDFA yang negara awalnya hanya memiliki transisi epsilon ke negara penerima dan memiliki transisi epsilon ke setiap negara penerima).> ≥
sumber
Sunting: Bukti kelengkapan PSPACE lengkap (disederhanakan) muncul di bawah ini.
Dua pembaruan. Pertama, bentuk normal yang dijelaskan dalam jawaban saya yang lain sudah muncul di sebuah makalah oleh Calbrix dan Nivat berjudul Awalan dan bahasa periode rasional -langaugesω , sayangnya tidak tersedia online.
Kedua, memutuskan apakah suatu bahasa melingkar mengingat DFA-nya adalah PSPACE-complete.
Edaran di PSPACE. Karena NPSPACE = PSPACE oleh teorema Savitch, cukuplah untuk memberikan algoritma NPSPACE untuk non-sirkularitas. Misalkan menjadi DFA dengan | Q | = n status. Fakta bahwa monoid sintaksis L ( A ) memiliki ukuran paling banyak n n menyiratkan bahwa jika L ( A ) tidak melingkar maka ada kata w panjang paling banyak n nA=(Q,Σ,δ,q0,F) |Q|=n L(A) nn L(A) w nn sedemikian rupa sehingga tetapi w k ∉ L ( A ) untuk beberapa k ≤ n . Algoritma menebak w dan menghitung δ w ( q ) = δ ( q , w ) untuk semua q ∈ Q , menggunakan O ( n log n ) spasi (digunakan untuk menghitung hingga n n ). Itu kemudian memverifikasi bahwa δ w (w∈L(A) wk∉L(A) k≤n w δw(q)=δ(q,w) q∈Q O(nlogn) nn tetapi δ ( k ) w ∉ F untuk beberapa k ≤ n .δw(q0)∈F δ(k)w∉F k≤n
Circularity adalah PSPACE-hard. Kozen menunjukkan dalam makalah klasiknya 1977 kertas Batas bawah untuk sistem bukti alami bahwa itu adalah PSPACE-sulit untuk memutuskan, diberi daftar DFA, apakah persimpangan bahasa yang diterima oleh mereka kosong. Kami mengurangi masalah ini menjadi bundar. Mengingat biner DFAs , kita menemukan seorang perdana p ∈ [ n , 2 n ] dan membangun terner DFA A menerima bahasa L ( A ) = ¯ { 2 w 1 2 w 2A1,…,An p∈[n,2n] A
(Dengan sedikit usaha lagi, kita dapat membuatbinerAjuga.) Tidaklah sulit untuk melihat (menggunakan fakta bahwapadalah prima) bahwaL(A)berbentuk lingkaran jika dan hanya jika persimpanganL(A1)∩⋯∩L(An)kosong.
sumber
Setiap dengan panjang p > 0 dapat ditulis sebagai x y i z di mana x = z = ϵ , y = w ≠ ϵ . Sudah jelas bahwa | x y | ≤ p dan | y | = | w | > 0 . Oleh karena itu bahasa digunakan untuk input yang tidak kosong, oleh lemma pemompaan.s∈L p>0 xyiz x=z=ϵ y=w≠ϵ |xy|≤p |y|=|w|>0
Untuk , definisi tersebut berlaku, karena NDFA yang menerima string kosong juga akan menerima sejumlah string kosong.w=ϵ
Penyatuan bahasa di atas adalah bahasa L dan karena bahasa biasa ditutup di bawah penyatuan, maka setiap bahasa melingkar teratur.
Dengan teorema Rice, tidak bisa dipastikan. Buktinya mirip dengan keteraturan.CIRCULARITY/TM
sumber