Ini adalah bukti standar dalam kursus automata bahwa untuk dan bahwa bukan bahasa bebas konteks.
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 ?
Apakah ada karakterisasi dari apa yang miliki tidak menjadi CFL?
context-free
Ryan
sumber
sumber
Jawaban:
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.L S(L)
Kondisi Dalam DFA minimum untuk L , setiap jalur penerimaan mengandung paling banyak satu loop.A L
Pengecualian: dua loop diizinkan jika label dan label awalannya sebelum loop pertama semua bepergian, dan akhiran setelah loop kedua kosong. Misalnya ok.aa∗b(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.u v t
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 .L xuy A u xunyxuny x u yx u y
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 nxuyv u,v xunyvmxunyvm x,u,v unxyunvmxyvm n kali (untuk kejadian ), baca x y , pop n kali, tekan m kali (untuk v ), baca x y , pop m kali.u xy n m v xy m
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.a∗b∗
Untuk saat ini bagian yang diperlukan hanyalah dugaan, dan lebih banyak pengecualian diperlukan untuk mendapatkan kondisi yang tepat, saya akan tertarik pada contoh tandingan.
sumber