Теория и реализация языков программирования

       

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


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

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

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

  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
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий