Регулярные множества и выражения
Введем понятие регулярного множества, играющего важную роль в теории формальных языков.
Регулярное множество в алфавите T определяется рекурсивно следующим образом:
- (пустое множество) - регулярное множество в алфавите T;
- {e} - регулярное множество в алфавите T (e - пустая цепочка);
- {a} - регулярное множество в алфавите T для каждого ;
- если P и Q - регулярные множества в алфавите T, то регулярными являются и множества
- ничто другое не является регулярным множеством в алфавите T.
Итак, множество в алфавите T регулярно тогда и только тогда, когда оно либо
, либо {e}, либо {a} для некоторого
, либо его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации.
Приведенное выше определение регулярного множества позволяет ввести следующую удобную форму его записи, называемую регулярным выражением.
Регулярное выражение в алфавите T и обозначаемое им регулярное множество в алфавите T определяются рекурсивно следующим образом:
- регулярное выражение, обозначающее регулярное множество ;
- {e} - регулярное выражение, обозначающее регулярное множество {e};
- {a} - регулярное выражение, обозначающее регулярное множество {a};
- если p и q - регулярные выражения, обозначающие регулярные множества P и Q соответственно, то
- (p|q) - регулярное выражение, обозначающее регулярное множество ,
- (pq) - регулярное выражение, обозначающее регулярное множество PQ,
- (p*) - регулярное выражение, обозначающее регулярное множество P*;
- ничто другое не является регулярным выражением в алфавите T.
Мы будем опускать лишние скобки в регулярных выражениях, договорившись о том, что операция итерации имеет наивысший приоритет, затем идет операции конкатенации, наконец, операция объединения имеет наименьший приоритет.
Кроме того, мы будем пользоваться записью p+ для обозначения pp*. Таким образом, запись (a|((ba)(a*))) эквивалентна a|ba+.
Также, мы будем использовать запись L(r) для регулярного множества, обозначаемого регулярным выражением r.
Содержание Назад Вперед
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий