Czy istnieje kontekstowy, nieregularny język

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ć?

formal-languages context-free regular-languages

— Simon S.
źródło

Można odpowiedzieć tymi samymi technikami, co cs.stackexchange.com/questions/1549

— sdcvvc

Wskazówka: wszystkie języki zawierające alfabet mają bardzo proste zamknięcie Kleene.

— Raphael

Odpowiedzi:

jest pozbawiony kontekstu, ale nie regularny (klasyczny przykład). Podobnie jest . $L = \{a^n b^n \mid n\in\mathbb{N}\}$ $L' = \{a^n b^n \mid n\in\mathbb{N}\} \cup \{a,b\}$

jest regularne. $L'^\ast = \{a,b\}^\ast$

— Gilles „SO- przestań być zły”
źródło

Brutalna siła, ale ważna.

— Raphael

L^{'} = L

$L' = L$

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.