Karakterisasi yang bukan CFL?

16

Ini adalah bukti standar dalam kursus automata bahwa untuk dan bahwa bukan bahasa bebas konteks.L=Σ|Σ|2S(L)={ww:wL}

Juga benar bahwa untuk setiap terbatas , adalah terbatas (dan karena itu CFL). Saya menduga bahwa yang tak terbatas dan teratur tidak "cukup" untuk bukan CFL. Sunting : bagaimana dengan non-CFL ?LS(L)LS(L)L

Apakah ada karakterisasi dari apa yang miliki tidak menjadi CFL?LS(L)

Ryan
sumber
Jika saya mengerti dengan benar, pertanyaannya adalah memutuskan, diberi bahasa teratur L, apakah S(L) bebas konteks atau tidak.
J.-E.
2
1. Bisakah Anda memberi tahu kami lebih lanjut tentang karakterisasi seperti apa yang Anda cari? Apakah Anda mencari algoritma yang, mengingat L , memutuskan apakah S(L) bebas konteks? Apakah Anda mencari beberapa kondisi pada L yang cukup untuk memastikan S(L) akan bebas konteks? Bentuk apa yang ingin Anda karakterisasi? 2. Jika Anda tidak mendapatkan jawaban apa pun setelah beberapa hari dan lebih suka melihat ini di CSTheory.SE, jangan ragu untuk menandainya karena perhatian moderator dan minta dimigrasi.
DW
@ DW 1. Baik tidak apa-apa, tapi saya lebih suka kondisi yang cukup. 2. Terima kasih atas tipnya!
Ryan
1
@Ryan hanya kondisi yang cukup? Nah, inilah pasangannya: (a) L teratur dan untuk setiap dalam L , w = w R (b) L adalah CF dan untuk semua n , L Σ n kosong atau sama dengan Σ n . Ini jelas tidak perlu. Jika Anda tidak mendapatkan jawaban di sini, harap pindahkan pertanyaan ke cstheory. Saya benar-benar ingin tahu tentang kondisi yang diperlukan dan memadai! wLw=wRnLΣnΣn
aelguindy
terhingga dan teratur memang tidak cukup untuk S ( L ) bukan CF. Jika Σ = { a , b , c } , L = a * kemudian S ( L ) = ( a a ) * yang teratur, maka CF. LS(L)Σ={a,b,c},L=aS(L)=(aa)
chi

Jawaban:

2

Lebih dari komentar yang diperluas dengan dugaan, tetapi di sini adalah kondisi yang tampaknya menangkap masalah, dalam konteks biasa untuk S ( L ) menjadi bebas konteks.LS(L)

Kondisi Dalam DFA minimum untuk L , setiap jalur penerimaan mengandung paling banyak satu loop.AL

Pengecualian: dua loop diizinkan jika label dan label awalannya sebelum loop pertama semua bepergian, dan akhiran setelah loop kedua kosong. Misalnya ok.aab(aa)

Ingat bahwa dua kata dan v bolak-balik jika mereka adalah kekuatan dari kata yang sama t . Kita dapat mengasumsikan sufiks kosong, karena tidak boleh kosong dan bepergian dengan label loop kedua dalam DFA.uvt

Cukup Asumsikan kondisi ini, Anda membangun PDA untuk dengan memperlakukan setiap pola penerimaan x u y dari A di mana Anda memberi label loop sederhana. Kami ingin menerima kata-kata dalam bentuk x u n y x u n y . Kita membaca x , mendorong simbol untuk setiap kemunculan Anda , membaca y x , lalu memunculkan simbol untuk setiap kemunculan Anda , dan akhirnya membaca y .LxuyAuxunyxunyxuyxuy

Tentang pengecualian, jika kita berada dalam kasus ini, jalur penerimaan dasar adalah dari bentuk mana u , v adalah label loop. Kami menerima kata-kata dalam bentuk x u n y v m x u n y v m , tetapi dengan asumsi ( x , u , v komuter) itu sama dengan u n x y u n v m x y v m , yang dapat dilakukan oleh PDA: push nxuyvu,vxunyvmxunyvmx,u,vunxyunvmxyvmnkali (untuk kejadian ), baca x y , pop n kali, tekan m kali (untuk v ), baca x y , pop m kali.uxynmvxym

PDA terakhir adalah penyatuan PDA untuk setiap pola.

Diperlukan (handwaving) Jika ada jalan dengan dua loop, bahkan dalam kasus paling sederhana di mana Anda harus mengambil satu lalu yang lain (misalnya ), Anda harus ingat berapa kali masing-masing diambil, tetapi struktur tumpukan mencegah Anda untuk mengulanginya dalam urutan yang sama. Perhatikan bahwa fakta bahwa DFA minimal adalah penting dalam karakterisasi, untuk menghindari penggunaan dua loop ketika seseorang sudah cukup.ab

Untuk saat ini bagian yang diperlukan hanyalah dugaan, dan lebih banyak pengecualian diperlukan untuk mendapatkan kondisi yang tepat, saya akan tertarik pada contoh tandingan.

Denis
sumber
"dan kemudian membaca w lagi, muncul simbol untuk setiap lingkaran diambil dalam kejadian kedua dari kata" - tetapi ada jauh lebih banyak seperti ! Kecuali saya salah membaca argumen Anda. w
Ryan
@Ryan jumlah "pola" xuy di mana u label loop terbatas, jadi kita bisa menebak yang mana yang kita baca.
Denis
Saya mengedit untuk memperjelas bagian ini.
Denis
Kondisi ini mirip dengan saya dengan yang lain yang ada dalam pikiran saya: S (L) adalah bebas konteks jika tidak ada kata , sehingga w 1 dan w 2 tidak saling awalan satu sama lain dan u ( w 1 + w 2 ) * v L . u,v,w1,w2w1w2u(w1+w2)vL
Serigala
@holf Anda tampaknya tidak bekerja untuk ab
Denis