До сих пор мы встречались лишь с автоматными языками и накопили достаточно много средств для доказательства того, что некоторый язык является автоматным. Для этого, например, достаточно построить для него регулярное выражение или получить его с помощью различных рассмотренных выше операций из заведомо автоматных языков. В этом разделе мы установим некоторое необходимое условие, которому удовлетворяют все автоматные языки. После этого, проверив, что некоторый язык этому условию не удовлетворяет, можно заключить, что он не является автоматным.
Теорема 6.3. (о разрастании для автоматных языков)
Пусть L - бесконечный автоматный язык. Тогда существует такая константа n, что любое слово w
(Здесь y0= ?, y1=y, yi+1 = yiy).
Доказательство Так как язык L автоматный, то существует ДКА A=<?, Q, q0, F, ? >, распознающий L. Пусть |Q|= n и слово w=w1w2 … wk
в диаграмме A, который несет слово w. Очевидно, что среди первых (n+1) состояний этого пути хотя бы одно встречается дважды. Выберем первое из таких состояний q
Содержательно, эта теорема утверждает, что у всякого достаточно длинного слова из автоматного языка имеется непустое подслово, которое можно вырезать или повторить сколько угодно раз, оставаясь внутри языка. Как, используя теорему ref{th-razr}, доказать, что некоторый язык L не является автоматным? Это можно сделать, используя схему доказательства "от противного":