Математическая теория формальных языков
Определение регулярного выражения
Определение 5.1.1.
Регулярное выражение над алфавитом
определяется рекурсивно следующим образом: 0 является регулярным выражением; 1 является регулярным выражением; если , то a является регулярным выражением; если e и f являются регулярными выражениями, то ,
и
тоже являются регулярными выражениями.
Для экономии скобок будем считать, что операция *
связывает сильнее (то есть имеет более высокий приоритет), чем умножение, а умножение связывает сильнее, чем сложение. Вместо
часто пишут просто .
Пример 5.1.2.
Пусть . Тогда
является регулярным выражением над алфавитом .
Определение 5.1.3.
Каждое регулярное выражение e над алфавитом
задает (denotes, represents) некоторый язык над алфавитом
(обозначение ), определяемое рекурсивно следующим образом:
Заметим, что в правой части последнего выражения символом * обозначена итерация языка (см. определение 1.2.7).
Вместо
часто пишут просто e.
Пример 5.1.4.
Пусть . Согласно определению
Определение 5.1.5.
Язык L называется регулярным если он задается некоторым регулярным выражением.
Определение 5.1.6.
Пусть e - регулярное выражение. Тогда .
Упражнение 5.1.7. Упростить регулярное выражение ((a+bc)*)*
Упражнение 5.1.8. Найти праволинейную грамматику для языка ab*a
Упражнение 5.1.9. Найти праволинейную грамматику для языка ((a+b)a)*.
Упражнение 5.1.10. Найти полный детерминированный конечный автомат для языка (a+b)*(aab+abaa+abb)(a+b)*.
Упражнение 5.1.11. Найти полный детерминированный конечный автомат для языка (a+b)*(a(b+1)abb+baa)(a+b)*.
Упражнение 5.1.12. Найти полный детерминированный конечный автомат для языка (b+c)((ab)*c+(ba)*)*.
Упражнение 5.1.13. Найти полный детерминированный конечный автомат для языка (abab)+(aba)*.
Упражнение 5.1.14. Найти полный детерминированный конечный автомат для языка (c+(a+b+c)(b+a(b+c)*a))*(a+b+c).
