Регулярные множества и выражения

Введем понятие регулярного множества, играющего важную роль в теории формальных языков.

Регулярное множество в алфавите T определяется рекурсивно следующим образом:

1. 
   (пустое множество) - регулярное множество в алфавите T;
2. {e} - регулярное множество в алфавите T (e - пустая цепочка);
3. {a} - регулярное множество в алфавите T для каждого
   
   ;
4. если P и Q - регулярные множества в алфавите T, то регулярными являются и множества
   1. 
   2. 
   3. 

5. ничто другое не является регулярным множеством в алфавите T.

Итак, множество в алфавите T регулярно тогда и только тогда, когда оно либо

, либо {e}, либо {a} для некоторого , либо его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации.

Приведенное выше определение регулярного множества позволяет ввести следующую удобную форму его записи, называемую регулярным выражением.

Регулярное выражение в алфавите T и обозначаемое им регулярное множество в алфавите T определяются рекурсивно следующим образом:

1. 
   регулярное выражение, обозначающее регулярное множество
   
   ;
2. {e} - регулярное выражение, обозначающее регулярное множество {e};
3. {a} - регулярное выражение, обозначающее регулярное множество {a};
4. если p и q - регулярные выражения, обозначающие регулярные множества P и Q соответственно, то
   1. (p|q) - регулярное выражение, обозначающее регулярное множество
      
      ,
   2. (pq) - регулярное выражение, обозначающее регулярное множество PQ,
   3. (p*) - регулярное выражение, обозначающее регулярное множество P*;

5. ничто другое не является регулярным выражением в алфавите T.

Мы будем опускать лишние скобки в регулярных выражениях, договорившись о том, что операция итерации имеет наивысший приоритет, затем идет операции конкатенации, наконец, операция объединения имеет наименьший приоритет.

Кроме того, мы будем пользоваться записью p+ для обозначения pp*. Таким образом, запись (a|((ba)(a*))) эквивалентна a|ba+.

Также, мы будем использовать запись L(r) для регулярного множества, обозначаемого регулярным выражением r.

Содержание  Назад  Вперед

---

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

---