Apakah ada konteks gratis, bahasa non-reguler , untuk mana teratur?

13

Saya tahu bahwa ada bahasa non-reguler, sehingga teratur, tetapi semua contoh yang saya temukan adalah peka konteks tetapi tidak bebas konteks.L

Jika tidak ada, bagaimana Anda membuktikannya?

Simon S
sumber
1
Dapat dijawab dengan teknik yang sama seperti cs.stackexchange.com/questions/1549
sdcvvc
2
Petunjuk: semua bahasa yang mengandung alfabet memiliki penutupan Kleene yang sangat sederhana.
Raphael

Jawaban:

20

L={anbnnN} bebas konteks tetapi tidak teratur (contoh klasik). Begitu juga .L={anbnnN}{a,b}

L={a,b} teratur.

Gilles 'SANGAT berhenti menjadi jahat'
sumber
2
Brute-force, tetapi valid.
Raphael
, sebenarnya ...L=L
vonbrand