Теория и реализация языков программирования




Связь регулярных множеств, конечных автоматов и регулярных грамматик - часть 3


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

Теорема 3.4. (Лемма о разрастании для регулярных множеств). Пусть L - регулярное множество. Существует такая константа k, что если

w \in L

и

\mid \! w \! \mid \geq k
, то цепочку w можно представить в виде xyz, где
0 < \mid \! y \! \mid \leq k
и
xy^iz \in L
для всех
i \geq 0
.

Доказательство. Пусть M = (Q, ?, D, q0, F) - конечный автомат, допускающий L, то есть L(M) = L и k = |Q|. Пусть

w \in L
и
\mid \! w \! \mid \geq k
. Рассмотрим последовательность конфигураций, которые проходит автомат M, допуская цепочку w. Так как в ней по крайней мере k + 1 конфигурация, то среди первых k+1 конфигурации найдутся две с одинаковыми состояниями. Таким образом, получаем существование такой последовательности тактов, что

(q_0, xyz) \vdash^* (q_1, yz) \vdash^r (q_1, z) \vdash^* (q_2, e)

для некоторых

q_1 \in Q, q_2 \in F \; \text{и} \; 0 < r \leq k
. Отсюда
0 < \mid \! y \! \mid \leq n
. Но тогда для любого i > 0 автомат может проделать последовательность тактов
(q_0, xyz) \vdash^* (q_1, y^iz) \vdash^+ (q_1, y^{i-1}z) \ldots \vdash^+(q_1, yz) \vdash^+(q_1, z) \vdash^* (q_2, e)
Таким образом,
xy^iz \in L
для всех i
1. Случай i = 0 то есть
xy \in L
также очевиден.

С помощью леммы о разрастании можно показать, что не является регулярным множеством язык L={0n1n|n

1}.

Допустим, что L регулярен. Тогда для достаточно большого n0n1n можно представить в виде xyz, причем y

e и
xy^iz \in L
для всех i
0. Если
y \in 0^+
или
y \in 1^+
, то
xz = xy^0z \in L
. Если
y \in 0^+1^+
, то
xyyz \in L
. Получили противоречие. Следовательно, L не может быть регулярным множеством.




Содержание  Назад  Вперед