Gibt es eine kontextfreie, nicht reguläre Sprache

13

Ich weiß , dass es nicht-reguläre Sprachen, so dass regulär ist, aber alle Beispiele , die ich sind kontextsensitiv finde aber nicht kontextfrei.L

Falls es keine gibt, wie beweisen Sie das?

Simon S
quelle
1
Kann mit den gleichen Techniken beantwortet werden wie cs.stackexchange.com/questions/1549
sdcvvc
2
Hinweis: Alle Sprachen, die das Alphabet enthalten, haben einen sehr einfachen Kleene-Verschluss.
Raphael

Antworten:

20

ist kontextfrei, aber nicht regulär (klassisches Beispiel). Also ist L ' = { a n b nn N } { a , b } .L={anbnnN}L={anbnnN}{a,b}

ist regulär.L={a,b}

Gilles 'SO - hör auf böse zu sein'
quelle
2
Brute-Force, aber gültig.
Raphael
, eigentlich ...L=L
vonbrand