Теорема о разрастании для автоматных языков

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

Теорема 6.3. (о разрастании для автоматных языков)

Пусть L - бесконечный автоматный язык. Тогда существует такая константа n, что любое слово w

L длины |w| > n можно разбить на три части x, y и z так, что w = xyz и

|xy|
n;
|y| > 0;
для любого m
0 слово wm = x ym z принадлежит языку L.

(Здесь y0= ?, y1=y, yi+1 = yiy).

Доказательство Так как язык L автоматный, то существует ДКА A=<?, Q, q0, F, ? >, распознающий L. Пусть |Q|= n и слово w=w1w2 … wk

L имеет длину k > n. Рассмотрим путь

$p=(q_0=q_{i_0},q_{i_1}, \ldots , q_{i_k})$

в диаграмме A, который несет слово w. Очевидно, что среди первых (n+1) состояний этого пути хотя бы одно встречается дважды. Выберем первое из таких состояний q

Q. Тогда для некоторой пары чисел l < j

n имеем

$q_{i_l} =q_{i_j}= q$

. Пусть x=w1w2 … wl - это префикс w, который переводит q0 в

$q_{i_l}=q$

$y=w_{i+1}\ldots w_j$

- это подслово w, которое переводит

$q_{i_l}=q$

$q_{i_j}= q$

, и

$z = w_{j+1}\ldots w_k$

- это суффикс w, который переводит

$q_{i_j}= q$

$q_{i_k} \in F$

. x и z могут быть пусты, но |y| = j-l

1. Длина |xy| = j

n. Таким образом, условия (1) и (2) теоремы выполнены. Нетрудно убедиться и в выполнении условия (3). Действительно, выбросив из пути p цикл

$q_{i_l}=q, \ldots , q_{i_j},$

получим путь p0 из q0 в

$q_{i_k}\in F$

, который несет слово xz, а повторив этот цикл m раз, получим путь p0 из q0 в q{ik}

F, который несет слово xym z. Следовательно, для любого m

0 wm = x ym z

Содержательно, эта теорема утверждает, что у всякого достаточно длинного слова из автоматного языка имеется непустое подслово, которое можно вырезать или повторить сколько угодно раз, оставаясь внутри языка. Как, используя теорему ref{th-razr}, доказать, что некоторый язык L не является автоматным? Это можно сделать, используя схему доказательства "от противного":

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