§ 3. Регулярная алгебра

Способы комбинирования конечных распознавателей могут использоваться для проверки аксиом множеств, из которых могут развиваться алгебраические системы. Классическая система, известная как регулярная алгеб­ра, основана на трех операциях — объединении, пересе­чении и конкатенации, определенных на множестве строк. Уравнения в алгебре могут точно определять не­которые множества строк; эти множества являются ре­шением уравнений (п. 3.1). Результаты, вытекающие из решений, имеют непосредственное применение к аспек­там теории языков (п. 3.2).

3.1. Выражения и уравнения. Перед тем как дать формальное определение, мы введем две константы внут­ри системы. Существует множество строк и {Λ}, кото­рые обозначим символами 0 и 1 соответственно. Мы обо­сновываем их использование изображением конечных

распознавателей соответственно на рис. 9.16, а и b,

Р ис. 9.16

Определение. Пусть X — множество строк, представимое конечным распознавателем. Когда X называется регулярным выражением. Если X и Y обозначают мно­жества строк, представимых двумя определенными маши­нами, то (в силу определения построения конечных рас­познавателей) Х Y (далее будем писать X + Y), X* и XY также являются регулярными выражениями.

Разрешенные конструкции составных конечных автома­тов предполагают следующие аксиомы для работы с про­извольными регулярными выражениями А, В и С:

1) А + В = В + А;

2) А + (В + С) = (А + В) + С;

3) А + А = А

4) А + 0 = А;

5) А(ВС) = (АВ)С;

6) A1 = А = 1А;

7) А0 = 0 = 0А;

8) А(В + С) = АВ + АС;

9) (A + B)C = AB + BC;

10) 0* = 1;

11) А* = А + А*;

12) (A*)*=4*.

Такую алгебраическую систему называют регулярной ал­геброй.

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

Пример 3.1. Пусть A = {abⁿ: 0 ≤ n}. Это выраже­ние регулярно, так как является представимым для ма­шины М, изображенной на рис. 9.17, а.

Используя машину, изображенную на рис. 9.16, а, ко­торая распознает 0, и применяя подходящее построение, получим машину, изображенную па рис. 9.17,6, которая, очевидно, эквивалентна М. Следовательно, А = А + 0. //

Рис. 9.17

Пример 3.2. Используя A и 1, определяемые маши­нами, данными выше, и обычной конструкцией конкате­нации, получаем недетерминированный конечный распо­знаватель, изображенный на рис. 9.18, а, который будет представлять строки в регулярном выражении 1А. Эту машину делаем детерминированной (рис. 9.18,b), затем получаем машину (рис. 9.18,с), эквивалентную М, кото­рая удовлетворяет (в данном случае) части аксиомы 6), а именно 1А = А. //

Определив регулярную алгебру, посмотрим, как ее ис­пользовать. Предположим, что А, В и С являются задан­ными регулярными выражениями (множествами строк) и что X и Y — неизвестные регулярные выражения та­кие, что выполнены следующие соотношения:

X = AX + BY, Y = ХС + В.

Существуют ли решения этих «уравнений», и если да, то как их найти? Как мы вскоре увидим, регулярные

Рис. 9.18

уравнения не имеют единственного решения; поэтому мы вначале введем понятие аппроксимации для регулярных выражений.

Определение. Для регулярных выражений X и Y отношение ≤ определяем следующим образом:

X ≤ Y (X аппроксимирует Y), если X + Y = Y. //

Теорема. Отношение определенное над регуляр­ными выражениями, является отношением порядка.

Доказательство.

Транзитивность имеет место, так как

X ≤ Y, Y ≤ Z X + Y = Y, Y + Z = Z. (*)

Поэтому

X + Z = X+(Y + Z) = (X + Y) + Z = Y + Z = Z

и, следовательно, X ≤ Z.

Антисимметричность имеет место, поскольку

X ≤ Y, Y ≤ Х Y = Х + Y= Y+ Х = Х.

Рефлективность следует из X + X = X. //

Отсюда также следует, что X ≤ Y ZX ≤ ZY для ре­гулярных выражений X, Y и Z, однако детали доказа­тельства оставим в качестве упражнения.

Перед тем как рассматривать уравнения, напомним, что из определения операции замыкания следует

А* = А0 + А¹ + ... + А^п + ... =

где А⁰ = 1. Это соотношение оказывается полезным при доказательстве следующих утверждений.

Лемма. Пусть Y и Z — решения регулярного урав­нения X = АХ + В. Тогда

а) В ≤ Y,

б) AY ≤ Y,

в) Y + Z — решение. Доказательство.

а) Так как Y — решение уравнения , то , и поэтому

Y + B=(AY + B)+B = AY + (B + B) = AY + B=Y,

Следовательно, В ≤ Y.

б) Аналогично Y + AY = (В + AY) + AY = В + AY = Y. Следовательно, AY ≤ Y.

в) Имеем

Y + Z = AY + B + AZ + B = A(Y + Z) + B. //

Уже достаточно много сказано о свойствах решений уравнения, однако существует ли хотя бы одно решение?

Лемма. является решением уравнения X = АХ + В.

Д о к а з а т е л ь с т в о. Подставляя в уравнение, имеем

А (А*В) + В = (А А* + А⁰) В = В =

= В = В = А*В. //

Теорема. является наименьшим (по отношению к решением регулярного уравнения .

Доказательство. Из лемм следует, что А*В — решение, и если Y — какое-либо другое решение, то В ≤ У, AB ≤ AY ≤ Y. Поэтому АВ ≤ У, АⁿВ ≤ У, и, добавляя неравенства для всех n ∈ N {0}, получаем А*В ≤ У. Следовательно, утверждение теоремы верно. //

Заметим, что А*В — это множество строк, каждая из которых является решением уравнения; если А = {а} и В = {М, то все строки вида аⁿb также являются решениями.

Заметим также, что так как А*В является наименьшим решением уравнения X = АХ + В, то оно является наи­меньшим выражением таким, что X → АХ + В совпа­дает с тождественным отображением. Поэтому его также называют наименьшей стационарной точкой уравнения (или минимальной стационарной точкой).

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

Теорема. Для заданных регулярных выражений А и В уравнение X = АХ + В эквивалентно паре уравне­ний

X = YB, Y = YA + 1

в том смысле, что они имеют одно и то же наименьшее решение, и это решение есть Х = А*В. //

Теорема. Для заданных регулярных выражений А и В уравнение X = АХ + В эквивалентно паре уравнений

X = BY, Y = AY + 1.

(В этом случае обе системы наименьшее решение Х = ВА*.) //

Эти две теоремы позволяют нам преобразовывать пра­вые линейные формы (X = АХ + В) в левые линейные формы (Х = ХА+В), которые соответствуют правым и левым рекурсиям внутри регулярных грамматик. Детали этого соответствия даны в п. 3.2, однако сначала мы обоб­щим результаты на системы алгебраических уравнений.

П редположим, что X₁, ..., Х_n — неизвестные регуляр­ные выражения и что A_ij (1 ≤ i, j ≤ n) и В₁, ..., В_п — известные регулярные выражения такие, что

Теперь можно использовать операции, определенные на регулярных выражениях, чтобы ввести операции на мат­рицах из регулярных выражений:

(С + D)_ij = C_ij + D_ij,

(СD)_ij =

С ≤ D тогда и только тогда, когда C_ij ≤ D_ij для всех i, j, где С и D — согласованные матрицы, элементы которых являются регулярными выражениями. Обозначив через X «регулярную матрицу», мы можем представить приве­денные выше уравнения в виде

X = ХА + В.

Применяя рассуждения, аналогичные тем, которые ис­пользовались в случае одного уравнения, можно показать, что эта система имеет минимальную стационарную точку ВА*, которая достигается на решениях X = BY, где Y = AY + I; I — единичная матрица. Соответствующие ре­зультаты справедливы для правых линейных систем. Из замечаний следует, что эти системы эквивалентны. Это помогает удалению левых рекурсий в контекстно-свобод­ных грамматиках.

Ясно, что для уравнения X «= ХА + В решение может быть определено как

X_i = (BY)_i =

где

Y_i = (AY + I)_ij =

Пример 4.4 гл. 8 показывает, как этот результат пе­реносится на контекстно-свободные грамматики. Преобра­зования, используемые в этом примере (хотя они и не строго обоснованы), появились при помощи рассуждений по аналогии. Мы завершаем этот раздел, указывая на формальную связь между регулярной алгеброй конечных распознавателей и регулярными грамматиками.

3.2. Представления регулярных грамматик. Напомним, в гл. 8 структурная грамматика G=(N, Т, Р, S) назы­валась грамматикой Хомского типа 3 или (Λ-свободной) регулярной грамматикой, если все элементы Р имели вид А → х или А → хВ, где х ⊆ Т и А, В ⊆ N, или же (если Λ ⊆ L(G)) S → Λ; в этом случае S не встречается ни в какой правой части.

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

Основной результат состоит из двух частей и дан в виде теоремы с конструктивным доказательством. Часть I является непосредственной, так как каждый пе­реход определяют на всей его области определения; в части 11 не обязательно, чтобы грамматика (N, Т, Р, S) для данных X ∈ N и а ∈ T имела продукцию вида X → а или X → aY при некотором Y ∈ N.

Теорема. Множество, представимое конечным ав~ томатом, является в точности таким же, как если бы вы­водилось из регулярных грамматик.

Доказательство. Опишем конструкции доказа­тельства.

Вначале рассмотрим конечный автомат М = (Q, ∑, t, g, F). Теперь построим регулярную грамматику G=(N, Т, Р, S). Если Λ∉ А (М), то можно сделать следующее. Пусть N = Q, Т = ∑ и S = q; построим Р такое, что

P = {X→aY, Y ∈ t(X, а)} {X → a, t(X, a) F },

Если Λ ∈ А(М), то расширяем конструкцию, создавая новый детерминал q, полагая S — q и добавляя к Р про­дукции

S → Λ,

S → aY (если Y ∈ t(q, а)),

S → a (если t(q, а) F = 0).

Сейчас легко показать, что для каждого x ∈ ∑ усло­вие х ∈ А (М) выполнено тогда и только тогда, когда х ∈ L(G). Очевидно, что если q ∈ F, то А представимо ав­томатом М и S → Λ — продукция G в наоборот. Если также а ∈ А (М) и |а| = п, то

а = а₁а₂ ... а_n, a_i ∈ ∑,

и поэтому существует путь в графе М, как показано на

Рис. 9.19

рис. 9.19. Здесь A_i ∈ N (не обязательно все различны) и B ∈ F, и но построению (рис. 9.20). Таким образом, a ∈ L(G). Проводя рассу­ждения в обратном порядке, аналогично получаем L(G) ⊆ A(M) и, следовательно, равенство доказано.

Сейчас надо показать, что для данной (Λ-свободной) регулярной грамматики предложения этой грамматики могут быть представимы некоторым конечным автоматом, а все другие строки не представимы этим автоматом. Возьмем G₁ = (N₁, Т₁, Р₁, S₁) и построим M₁ = (Q₁, ∑₁, t₁, q₁, F₁) как показано далее. Пусть ∑₁ = Т₁ и Q₁ = N₁ {τ} {π} (где τ и π — специальные символы, ко­торых нет в N₁; τ представляет правильную терминаль­ную строку, а π представляет ошибку), q₁ = S₁ и F₁ = {τ}. Если также Λ ∈ L(G₁), т. е S₁ → Λ принадлежит Р₁, то F₁ = {τ, q₁}. Окончательно имеем

Рис.9.20 Рис. 9.21

t₁ = {((X, a), Y): X→ aY есть в Р₁}

{((X, а), τ): X → а есть в P₁)

{(( τ, а), π) для всех а ∈ ∑₁}

{((X, b), π): если X N₁ и не X → bY для любого Y ∈ N₁, и не выполняется условие X → b есть в P₁}

{(( π, а), π) для всех а ∈ ∑₁}.

Обоснование того факта, что эта машина представляет L(G₁), оставляем в качестве упражнения. //

Пример 3.3. Пусть задана регулярная грамматика G =({A, В, С, D}, {х, у, z}, Р, А), где

P = {А → Λ |хВ| уС, В → zB |y| уС, С → xD, D → yD|x}.

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

Упражнение 9.3.

1. Пусть заданы регулярные выражения А, В, С и D такие, что A ≤ С и В ≤ С. Доказать, что

а) А + D ≤ С + D; б) AD ≤ CD;

в) DA ≤ DC; г) А* ≤ С*; д) А + В ≤ С.

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

3. Определить конечный автомат для языка L, опреде­ленного как 11*01* (т. е. L = {w ∈ {0, 1}*: w} начинает­ся с 1 и имеет только один нуль. Выписать правую ли­нейную грамматику, определяемую этим автоматом, и по­следовательность перемещений, делающих представимой строку 111011.