Уравнения с регулярными коэффициентами

Предварительные сведения.

Пусть p, q и r — регулярные выражения. Тогда справедливы следующие соотношения (употребляемые ниже знаки | и + равнозначны):

\begin{matrix}(1) & p|q = q|p; & (7) & pe = ep = p; \\ (2) & ∅^{∗} = e; & (8) & ∅p = p∅ = ∅; \\ (3) & p|(q|r) = (p|q)|r; & (9) & p^{∗} = p|p^{∗}; \\ (4) & p(qr) = (pq)r; & (10) & (p^{∗})^{∗} = p^{∗}; \\ (5) & p(q|r) = pq|pr; & (11) & p|p = p; \\ (6) & (p|q)r = pr|qr; & (12) & p|∅ = p. \end{matrix}

* * *

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

Рассмотрим, например, уравнение с регулярными коэффициентами

X = aX + b  (2.2.1)

где a и b – регулярные выражения. Легко проверить прямой подстановкой, что X = a^{∗}b – решение уравнения (2.2.1). Иначе говоря, если в обе части уравнения (2.2.1) подставить a^{∗}b вместо X, то слева и справа будет одно и то же множество.

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

X = a_{1}X + a_{2}Y + a_{3}  (2.2.2)
Y = b_{1}X + b_{2}Y + b_{3}

где a_{i} и b_{i} для всех i = 1, 2, 3 являются регулярными выражениями. Покажем, как решить эту систему уравнений и получить решение

X = (a_{1} + a_{2}b_{2}^{∗}b_{1})^{∗}(a_{3} + a_{2}b_{2}^{∗}b_{3})
Y = (b_{2} + b_{1}a_{1}^{∗}a_{2})^{∗}(b_{3} + b_{1}a_{1}^{∗}a_{3})

Однако сначала отметим, что не все уравнения с регулярными коэффициентами обладают единственным решением. Например, если

X = αX + β  (2.2.3)

– уравнение с регулярными коэффициентами и α обозначает множество, содержащее пустую цепочку, то X = α^{∗}(β + γ) будет решением уравнения (2.2.3) для любого γ (γ не обязано даже быть регулярным, см. упр. 2.2.7). Таким образом, уравнение (2.2.3) имеет бесконечно много решений. В такого рода ситуациях мы будем брать наименьшее решение, которое назовём наименьшей неподвижной точкой. Наименьшая неподвижная точка уравнения (2.2.3) – это множество X = α^{∗}β.

Определение. Систему уравнений с регулярными коэффициентами назовём стандартной системой с множеством неизвестных Δ = {X_{1}, X_{2}, …, X_{n}}, если она имеет вид X_{1} = α_{10} + α_{11}X_{1} + α_{12}X_{2} + … + α_{1n}X_{n} … X_{n} = α_{n0} + α_{n1}X_{1} + α_{n2}X_{2} + … + α_{nn}X_{n} – где все α_{ij} – регулярные

выражения в алфавите, не пересекающемся с Δ.

Коэффициентами уравнений являются выражения α_{ij}. Заметим, что если α_{ij} = ∅ (такое регулярное выражение возможно), то в уравнении для X_{i} нет члена, содержащего X_{j}. Аналогично, если α_{ij} = ε, то в уравнении для X_{i} член, содержащий X_{j}, – это просто X_{j}. Иными словами, ∅ играет роль коэффициента 0, а ε – роль коэффициента 1 в обычных линейных уравнениях.

Алгоритм 2.1. Решение стандартной системы уравнений с регулярными коэффициентами.

Вход. Стандартная система Q уравнений с регулярными коэффициентами в алфавите Σ и с множеством неизвестных Δ = {X_{1}, X_{2}, …, X_{n}}.

Выход. Решение системы Q в виде X_{1} = α_{1}, …, X_{n} = α_{n}, где α_{i} – регулярное выражение в алфавите Σ.

Метод. Метод напоминает решение системы линейных уравнений методом исключения Гаусса.

Шаг 1. Положить i = 1.

Шаг 2. Если i = n, перейти к шагу 4. В противном случае с помощью тождеств леммы 2.1 записать уравнение для X_{i} в виде X_{i} = αX_{i} + β, где α – регулярное выражение в алфавите Σ, а β - регулярное выражение вида β_{0} + β_{i}X_{i+1} + … + β_{n}X_{n}, причём все β_{i} – регулярные выражения в алфавите Σ. (Мы увидим, что это всегда возможно.) Затем в правых частях уравнений для X_{i+1}, …, X_{n} заменить X_{i} регулярным выражением α^{∗}β.

Шаг 3. Увеличить i на 1 и вернуться к шагу 2.

Шаг 4. Записать уравнение для X_{n} в виде X_{n} = αX_{n} + β, где α и β – регулярные выражения в алфавите Σ. (После выполнения шага 2 для каждого i < n в правой части уравнения для X_{i} не будет неизвестных X_{1}, …, X_{i−1}. В частности, на шаге 4 этим свойством будет обладать и уравнение для X_{n}). Перейти к шагу 5 (при этом i = n).

Шаг 5. Уравнение для X_{i} имеет вид X_{i} = αX_{i} + β, где α и β – регулярные выражения в алфавите Σ. Записать на выходе X_{i} = α^{∗}β и в уравнения для X_{i−1}, …, X_{1} подставить α^{∗}β вместо X_{i}.

Шаг 6. Если i = 1, остановиться. В противном случае уменьшить i на 1 и вернуться к шагу 5.

Пример 2.9. Пусть Δ = {X_{1}, X_{2}, X_{3}}. Рассмотрим систему уравнений

X_{1} = 0X_{2} + 1X_{1} + ε  (2.2.4)

X_{2} = 0X_{3} + 1X_{2}  (2.2.5)
X_{3} = 0X_{1} + 1X_{3}  (2.2.6)

Из уравнения (2.2.4) получаем X_{1} = 1X_{1} +(0X_{2} +ε). Затем в остальные уравнения подставляем 1^{∗}(0X_{2}+ε) вместо X_{1}. Уравнение (2.2.6) принимает вид

X_{3} = 01^{∗}(0X_{2} + ε) + 1X_{3}

или с учётом леммы 2.1

X_{3} = 01^{∗}0X_{2} + 1X_{3} + 01^{∗}  (2.2.7)

Если теперь из уравнения (2.2.5), которое мы ещё не трогали, выразить X_{2} через X_{3} и в (2.2.7) подставить 1^{∗}0X_{3} вместо X_{2}, то получим

X_{3} = (01^{∗}01^{∗}0 + 1)X_{3} + 01^{∗}  (2.2.8)

Теперь в алгоритме 2.1 мы дошли до шага 5. Из уравнения (2.2.8) находим решение для X_{3}:

X_{3} = (01^{∗}01^{∗}0 + 1)^{∗}01^{∗}  (2.2.9)

Подстановка (2.2.9) в (2.2.5) даёт

X_{2} = 0(01^{∗}01^{∗}0 + 1)^{∗}01^{∗} + 1X_{2}  (2.2.10)

Так как X_{3} не входит в уравнение (2.2.4), то оно не меняется. Затем решаем (2.2.10) и получаем

X_{2} = 1^{∗}0(01^{∗}01^{∗}0 + 1)^{∗}01^{∗}  (2.2.11)

Подставляем (2.2.11) в (2.2.4):

X_{1} = 01^{∗}0(01^{∗}01^{∗}0 + 1)^{∗}01^{∗} + 1X_{1} + ε  (2.2.12)

Решением уравнения (2.2.12) будет

X_{1} = 1^{∗}(01^{∗}0(01^{∗}01^{∗}0 + 1)^{∗}01^{∗} + ε)  (2.2.13)

Выход алгоритма 2.1 – равенства (2.2.9), (2.2.11) и (2.2.13).

Мы должны показать, что выход алгоритма 2.1 действительно является решением данной системы уравнений в том смысле, что если подставить решение вместо неизвестных, то в каждом уравнении обе его части будут обозначать одно и то же множество. Как уже указывалось, решение стандартной системы уравнений не всегда единственно. Однако мы увидим, что в таком случае алгоритм 2.1 даёт наименьшую неподвижную точку.

Определение. Пусть Q – стандартная система уравнений с множеством неизвестных Δ и с коэффициентами в алфавите Σ. Отображение f множества Δ в множество языков в алфавите Σ называют решением системы Q, если после подстановки в каждое уравнение f(X) вместо X для каждого X ∈ Δ уравнения становятся равенствами множеств. Отображение f : Δ → P (Σ^{∗}) называют наименьшей неподвижной точкой системы Q, если f – решение и для любого другого решения g

f(X) ⊆ g(X) для всех X ∈ Δ

Следующие две леммы содержат полезные сведения о наименьших неподвижных точках.

Лемма 2.2. Каждая стандартная система уравнений Q с неизвестными Δ обладает единственной наименьшей неподвижной точкой.

Доказательство. Пусть f(X) = {w|w ∈ g(X) для всех решений g системы Q} для всех X ∈ Δ. Можно прямо показать, что f – решение и f(X) ⊆ g(X) для всех решений g. Таким образом, f – единственная наименьшая неподвижная точка системы Q.

Теперь дадим некоторую характеристику наименьшей неподвижной точки.

Лемма 2.3. Пусть Q – стандартная система уравнений с неизвестными Δ = X_{1} … X_{n} и уравнение для X_{i} имеет вид

X_{i} = α_{i0} + α_{i1}X_{1} + α_{i2}X_{2} + … + α_{in}X_{n}

Тогда наименьшей неподвижной точкой системы Q будет такое отображение f, что f(X_{i}) = {w_{1} … w_{m}|w_{m} ∈ α_{i_{m}0} и w_{k} ∈ α_{j_{k}j_{k+1}} для некоторой последовательности чисел j_{1}, …, j_{m}, где m ⩾ 1, 1 ⩽ k ⩽ m и j_{1} = i}.

Доказательство. Легко проверить непосредственно, что для всех i

f(X_{i}) = α_{i0} ∪ α_{i1}f(X_{1}) ∪ … ∪ α_{in}f(X_{n})

Таким образом, f – решение.

Чтобы показать, что f – наименьшая неподвижная точка, предположим, что g – решение и для некоторого i существует цепочка w ∈ f(X_{i}) − g(X_{i}). Так как w ∈ f(X_{i}), то можно записать w = w_{1} … w_{m}, где для некоторой последовательности чисел j_{1}, …, j_{m} выполнены условия w_{m} ∈ α_{i_{m}0} и w_{k} ∈ α_{j_{k}j_{k+1}} для 1 ⩽ k ⩽ m и j_{1} = i. Так как g – решение, то

g(X_{j}) = α_{j0} ∪ α_{j1} g(X_{1}) ∪ … ∪ α_{jn} g(X_{n}) для всех j

В частности, α_{j0} ⊆ g(X_{j}) и α_{jk} g(X_{k}) ⊆ g(X_{j}) для всех j и k. Тогда w_{m} ∈ g(X_{j_{m}}), w_{m−1}w_{m} ∈ g(X_{j_{m−1}}) и т.д. В конечном счёте получаем, что цепочки w = w_{1}w_{2} … w_{m} принадлежат множеству g(X_{j_{1}}) = g(X_{i}). Пришли к противоречию, так как предположили, что w не принадлежит g(X_{i}). Таким образом, заключаем, что f(X_{i}) ⊆ g(X_{i}) для всех i.

Отсюда непосредственно следует, что f – наименьшая неподвижная точка системы Q.

Лемма 2.4. Пусть Q_{1} и Q_{2} – системы уравнений до и после одного применения шага 2 алгоритма 2.1. Тогда Q_{1} и Q_{2} имеют одну и ту же наименьшую неподвижную точку.

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

Лемма 2.5. Пусть Q_{1} и Q_{2} – системы уравнений до и после одного применения шага 5 алгоритма 2.1. Тогда Q_{1} и Q_{2} имеют одну и ту же наименьшую неподвижную точку.

Доказательство (предоставлялось читателям).

Теорема 2.1. Алгоритм 2.1 находит наименьшую неподвижную точку стандартной системы уравнений.

Доказательство. После того как шаг 5 применён для всех i, все уравнения принимают вид X_{i} = α_{i}, где α_{i} – регулярное выражение в алфавите Σ. Ясно, что отображение f, для которого f(X_{i}) = α_{i}, и будет наименьшей неподвижной точкой этой системы.

ЛИТЕРАТУРА

1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.:Мир, 1978 г. Т. 1. С. 126–131.