Теоретические основы грамматики по регулярным выражениям

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

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

Способ их описания — регулярные выражения и недетерминированные конечные автоматы, допускающие цепочки из этих множеств.

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

РQ — конкатенация.

PV* и QV*: PQ, = {pq | pP, qQ.};

Р* - итерация.

PV*: Р* = {р* | pP}.

Тогда для алфавита V регулярные множества определяются рекурсивно:

• 1. — регулярное множество.
• 2. {} - регулярное множество.
• 3. {а} - регулярное множество aV.
• 4. Если Р и Q, — произвольные регулярные множества, то множества PQ, PQ и Р* также являются регулярными множествами.
• 5. Ничто другое не является регулярным множеством.

Фактически регулярные множества — это множества цепочек символов над заданным алфавитом, построенные определенным образом (с использованием операций объединения, конкатенации и итерации). Все регулярные языки представляют собой регулярные множества.

Три основных способа, с помощью которых можно задавать регулярные языки — это:

• -регулярные (праволинейные и леволинейные) грамматики,
• -конечные автоматы (КА) и
• -регулярные множества (равно как и обозначающие их регулярные выражения).

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

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

Утверждение 1. Язык является регулярным множеством тогда и только тогда, когда он задан леволинейной (праволинейной) грамматикой.

Утверждение 2. Язык может быть задан леволинейной (праволинейной) грамматикой тогда и только тогда, когда он является регулярным множеством.

Утверждение 3. Язык является регулярным множеством тогда и только тогда, когда он задан с помощью конечного автомата.

Утверждение 4. Язык распознается с помощью конечного автомата тогда и только тогда, когда он является регулярным множеством.

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

Свойства регулярных выражений Регулярные множества можно обозначать с помощью регулярных выражений. Эти обозначения вводятся следующим образом:

• 1. 0 — регулярное выражение, обозначающее .
• 2. — регулярное выражение, обозначающее {}.
• 3. а — регулярное выражение, обозначающее {a} aV.
• 4. Если р и q — регулярные выражения, обозначающие регулярные множества Р и Q, то p+q, pq, р* - регулярные выражения, обозначающие регулярные множества PQ, PQ и Р* соответственно.

Два регулярных выражения и равны, =, если они обозначают одно и то же множество.

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

При записи регулярных выражений будут использоваться круглые скобки, как и для обычных арифметических выражений. При отсутствии скобок операции выполняются слева на право с учетом приоритета. Приоритет для операций принят следующий: первой выполняется итерация (высший приоритет), затем конкатенация, потом — объединение множеств (низший приоритет).

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

• 1. +* = +* = *
• 2. + = +.
• 3. +(+) = (+)+
• 4. (+) = +
• 5. (+) = +
• 6. () = ()
• 7. + =
• 8. +* = *
• 9. +* = *+ = a*
• 10. 0* =
• 11. 0 = 0 = 0
• 12. 0+ = +0 =
• 13. = =
• 14. (*)* = *

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

Следует также обратить внимание на то, что среди прочих свойств отсутствует равенство =, то есть операция конкатенации не обладает свойством коммутативности. Это и не удивительно, поскольку для этой операции важен порядок следования символов.