Czy istnieje kontekstowy, nieregularny język

13

Wiem, że istnieją nieregularne języki, więc jest regularny, ale wszystkie przykłady, które mogę znaleźć, są zależne od kontekstu, ale nie pozbawione kontekstu.L

Jeśli nie ma, jak to udowodnić?

Simon S.
źródło
1
Można odpowiedzieć tymi samymi technikami, co cs.stackexchange.com/questions/1549
sdcvvc
2
Wskazówka: wszystkie języki zawierające alfabet mają bardzo proste zamknięcie Kleene.
Raphael

Odpowiedzi:

20

jest pozbawiony kontekstu, ale nie regularny (klasyczny przykład). Podobnie jest L = { a n b nn N } { a , b } .L={anbnnN}L={anbnnN}{a,b}

jest regularne.L={a,b}

Gilles „SO- przestań być zły”
źródło
2
Brutalna siła, ale ważna.
Raphael
L=L