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




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


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

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

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

    1. P \cup Q (объединение),
    2. PQ \; ( \text{конкатенация, то есть множество} \; \{pq \! \mid \! p \in P, \; q \in Q\})
    3. P^* \; (\text{итерация:} \; P^*=\bigcup\limits^\infty_{n=0} \; P^n);

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

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

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

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

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

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

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

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

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

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

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




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