Доказательство. Итак, пусть автоматный язык L содержит бесконечное число цепочек

Итак, пусть автоматный язык L содержит бесконечное число цепочек.

Предположим, что L распознается детерминированным конечным автоматом A с n состояниями.

Для проверки заключения леммы выберем произвольную цепочку α этого языка, которая имеет длину n.

Если конечный автомат A распознает L, то цепочка α допускается этим автоматом, то есть в автомате A существует путь длины n из начального в одно из заключительных состояний, помеченный символами цепочки α. Путь этот не может быть простым, он должен проходить ровно через n + 1 состояние, в то время как автомат A имеет n состояний. Это значит, что этот путь проходит по меньшей мере два раза через одно и то же состояние автомата A, то есть на этом пути есть цикл с повторяющимся состоянием. Пусть это повторяющееся состояние q_k.

Разделим цепочку α на три части, так что α = uvw, где v – подцепочка, переводящая A из состояния q_k опять в состояние q_k, и w – подцепочка, переводящая A из состояния q_k в заключительное состояние. Заметим, что как u, так и w могут быть пустыми, но подцепочка v не может быть пустой. Но тогда очевидно, что автомат A должен допускать также и цепочку uvvw, поскольку повторяющаяся подцепочка v снова проходит по циклическому пути из q_k в q_k, а также и цепочку uvvvw, и любую вида uvv...vw.

Это рассуждение и составляет доказательство леммы о накачке.

Дата добавления: 2015-07-26; просмотров: 161; Нарушение авторских прав

Мы поможем в написании ваших работ!