Регулярные выражения и регулярные множества - ещё один способ задания автоматного языка⁠⁠

Регулярные выражения и регулярные множества - ещё один способ задания автоматного языка.

Предыдущая статья: Синтаксические диаграммы автоматных языков - рисунок порядка автоматных языков. в vk.com

Ещё одним способом задать язык является регулярное выражение. Регулярным выражением обозначают множество цепочек, которое называют регулярное множество. Чтобы задать регулярное выражение для некого алфавита Σ следуют учитывать 6 правил:

1. Отдельный символ из алфавита Σ есть регулярное выражение. Например символ а ∈ Σ (символ из алфавита Σ) задаёт множество {а}.

2. Пустая цепочка ε есть регулярное выражение, задаёт множество {ε}

3. Если R и Q - регулярные выражения, то запись RQ тоже регулярное выражение, которое обозначает сцеплённое множество, где первая цепочка пары образуется выражением R, а вторая выражением Q. Сцепление ещё называют конкатенацией.

4. Если R и Q - регулярные выражения, то запись R | Q тоже регулярное выражение, которое обозначает объединение множеств цепочек заданных выражениями R и Q. | - знак читается как «или».

5. Если R регулярное выражение, то запись R* тоже регулярное выражение, которое обозначает множество, которое получается путём повторения цепочек множества заданное R. Повторение ещё называют итерация.

6. Если R регулярное выражение, то запись (R) тоже регулярное выражение и обозначает тоже самое множество, что и R.

Предполагаем приоритет операции, высший имеет «*» - повторение, затем сцепление и низший «|» («или»). Скобки используются для изменения порядка операций.

Зачастую при записи регулярного выражения запись ε опускают и вводится дополнительный оператор «один раз и более» обозначенный символом «⁺», что значит R⁺=RR*. Вот так это выглядит на примере языка целых чисел со знаком:

(+ | – | ) (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 )⁺

Теорема Клини гласит: Автоматные языки являются регулярными множествами. Регулярные множества являются автоматными языками.

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

И чтобы вам было проще понять правила сделаем таблицу соответствия правил с участками рисунка порядка (синтаксической диаграммы) языка.

На этом урок окончен. В следующем мы обсудим регулярные выражения на практике и подытожим тему автоматных языков. Новоиспечённые подписываемся, с нами интересно. Дайте пятюню.