Мне было интересно, какие наборы языков генерируются ограничениями регулярных выражений. Предположим, что все ограничения имеют постоянный символ для каждого элемента и конкатенации. Тогда восемь классов могут быть сформированы наличием или отсутствием дополнения / отрицания, изменения / объединения и звезды Клини. (Да, у «обычных» регулярных выражений нет оператора , но здесь это удобно.)
Выражения, допускающие чередование и звезду Клини, с дополнением или без него (что такое небольшой экспоненциальный взрыв среди друзей?), Генерируют обычные языки. Выражения, допускающие чередование и дополнение, но не звезду Клини, генерируют языки без звезд. Выражения, допускающие чередование, но не дополнение, или звезда Клини порождают конечные языки.
Но можно ли генерировать какие-либо интересные классы языков без чередования? Без любого из трех операторов все, что может быть сгенерировано, - это одно слово. Оператор дополнения здесь не сильно помогает.
Только со звездой Клини класс несколько интересен ... не ясно, могут ли они быть распознаны быстрее обычных языков. (Что-нибудь нетривиальное известно об этом?)
И со звездой Клини, и с дополнением ... у вас есть что-нибудь интересное? У этого класса есть имя?
Этот вопрос был вдохновлен вопросом регулярного выражения на math.se.
Ответы:
Класс регулярных языков , которые могут быть описаны регулярными выражениями без союза (и без комплементарности) известен как союз свободного регулярная (также: звезда-точка регулярна ) языков. Этот класс языков, по-видимому, недавно привлек к себе внимание:
Бенедек Надь: «Свободные от объединения регулярные языки и 1-циклические автоматы без путей», Publicationes Mathematicae 68 (1-2), 2006.
Сергей Афонин и Денис Голомазов: «Минимальные несвязные разложения регулярных языков», Теория языка и автоматов и приложения, Springer 2009.
Галина Йираскова и Томас Масопуст: «Сложность в регулярных языках, не состоящих в союзе», Развитие теории языка, Springer 2010.
источник