Структуры данных и модели вычислений
Регулярные выражения
Регулярные выражения — это аналитический (формульный) способ задания регулярных языков.
Определение.
Регулярным выражением над алфавитом называется выражение, построенное по следующим правилам:
- — регулярное выражение;
- — регулярное выражение;
- — регулярное выражение, если ;
- — регулярное выражение, если
и — регулярные выражения;
- — регулярное выражение, если и — регулярные выражения;
- — регулярное выражение, если — регулярное выражение.
Регулярное выражение задает язык в соответствии со следующими правилами:
- — пустой язык;
- — язык, состоящий из одного пустого слова;
- — язык, состоящий из одного однобуквенного слова ;
- ;
- ;
- .
Пример.
Рассмотрим регулярное выражение
над алфавитом . Язык состоит из слов, в которых на нечетных местах стоит символ , а на четных или .
Замечание 1.
В регулярных выражениях вместо знака "" часто используют знак "".
Замечание 2.
Если дополнить правила построения регулярных выражений еще двумя правилами
- — регулярное выражение, если
и — регулярные выражения,
- — регулярное выражение, если — регулярное выражение, и , а ,
то получим так называемые расширенные регулярные выражения. Здесь дополнение берется до множества всех слов в алфавите . Если не использовать дополнение, то получим полурасширенное регулярное выражение.
Как увидим в дальнейшем, использование расширенных регулярных выражений не расширяет класса регулярных языков.
Замечание 3.
Используя описанную выше интерпретацию регулярных выражений, мы будем вместо соотношения
писать .
