Zastanawiałem się, jakie zestawy języków są generowane przez ograniczenia wyrażeń regularnych. Załóżmy, że wszystkie ograniczenia mają stały symbol dla każdego elementui konkatenacja. Następnie można utworzyć osiem klas poprzez obecność lub brak dopełniacza / negacji, zmiany / unii i gwiazdy Kleene. (Tak, „normalne” wyrażenia regularne nie mają operator, ale tutaj jest to wygodne).
Wyrażenia pozwalające na przemianę i gwiazdę Kleene, z dopełnieniem lub bez (co jest małym podwójnym wykładniczym powiększeniem wśród przyjaciół?), Generują zwykłe języki. Wyrażenia umożliwiające zmianę i uzupełnienie, ale nie gwiazdę Kleene, generują języki bez gwiazdek. Wyrażenia pozwalające na zmianę, ale nie na uzupełnienie lub gwiazda Kleene generują skończone języki.
Ale czy można generować ciekawe klasy języków bez zmian? Bez żadnego z trzech operatorów wszystko, co można wygenerować, to jedno słowo. Operator dopełniacza niewiele tu pomaga.
Z samą gwiazdą Kleene klasa jest nieco interesująca ... nie jest jasne, czy można je rozpoznać szybciej niż zwykłe języki. (Czy jest o tym coś nietypowego?)
Zarówno gwiazdą Kleene, jak i dopełnieniem ... otrzymujesz coś interesującego? Czy ta klasa ma imię?
To pytanie zostało zainspirowane pytaniem wyrażenia regularnego na math.se.
Odpowiedzi:
Klasa języków regularnych, którą można opisać wyrażeniami regularnymi bez unii (i bez dopełnienia), znana jest jako bezzwiązkowa regularna (także: regularna kropka-gwiazda ). Ta klasa języków najwyraźniej ostatnio zyskała trochę uwagi:
Benedek Nagy: „Bezunijne języki regularne i automaty do 1 ścieżki bez cyklu”, Publicationes Mathematicae 68 (1-2), 2006.
Sergey Afonin i Denis Golomazov: „Minimalny bezunijny rozkład języków zwykłych”, Teoria języków i automatów oraz aplikacje, Springer 2009.
Galina Jirásková i Tomás Masopust: „Złożoność wolnych od Unii języków zwykłych”, Rozwój teorii języka, Springer 2010.
źródło