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

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

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

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

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

1. |xy|
   
   n;
2. |y| > 0;
3. для любого 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. Рассмотрим путь

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

Q. Тогда для некоторой пары чисел l < j n имеем . Пусть x=w1w2 … wl - это префикс w, который переводит q0 в , - это подслово w, которое переводит в , и - это суффикс w, который переводит в . x и z могут быть пусты, но |y| = j-l 1. Длина |xy| = j n. Таким образом, условия (1) и (2) теоремы выполнены. Нетрудно убедиться и в выполнении условия (3). Действительно, выбросив из пути p цикл получим путь p0 из q0 в , который несет слово xz, а повторив этот цикл m раз, получим путь p0 из q0 в q{ik} F, который несет слово xym z. Следовательно, для любого m 0 wm = x ym z L.

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

1. Предположим, что L автоматный язык. Тогда для него имеется константа n из утверждения теоремы ref{th-razr}.
2. Определим по n некотрое "специальное" слово w из L длины > n и докажем, что для любого разбиения w = xyz, удовлетворяющего условиям (1) и (2) теоремы, найдется такое k
   
   0, что слово wk=xyk z не принадлежит L.
3. На основании полученного противоречия делаем вывод, что L - не автоматный язык.

Разумеется, в этой схеме самым сложным является выбор "специального" слова w в пункте (2). Что касается, подбора такого k 0, для которого wk L, то, как правило, достаточно рассмотреть k = 0 или k = 2.


Содержание раздела

---

---