Структуры данных и модели вычислений


Регулярные выражения


Регулярные выражения — это аналитический (формульный) способ задания регулярных языков.

Определение.

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

  • — регулярное выражение;
  • — регулярное выражение;
  • — регулярное выражение, если ;
  • — регулярное выражение, если

    и — регулярные выражения;

  • — регулярное выражение, если и — регулярные выражения;
  • — регулярное выражение, если — регулярное выражение.

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

  • — пустой язык;
  • — язык, состоящий из одного пустого слова;
  • — язык, состоящий из одного однобуквенного слова ;
  • ;
  • ;
  • .

Пример.

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

над алфавитом . Язык состоит из слов, в которых на нечетных местах стоит символ , а на четных или .

Замечание 1.

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

Замечание 2.

Если дополнить правила построения регулярных выражений еще двумя правилами

  1. — регулярное выражение, если

    и — регулярные выражения,

  2. — регулярное выражение, если — регулярное выражение, и , а ,

то получим так называемые расширенные регулярные выражения. Здесь дополнение берется до множества всех слов в алфавите . Если не использовать дополнение, то получим полурасширенное регулярное выражение.

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

Замечание 3.

Используя описанную выше интерпретацию регулярных выражений, мы будем вместо соотношения

писать .




Начало  Назад  Вперед



Книжный магазин