Математическая теория формальных языков

       

Определение регулярного выражения


Определение 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).



Содержание раздела