Interested Article - Лемма о разрастании
![](/images/007/358/7358543/1.jpg?rand=69263)
![](https://cdn.wafarin.com/avatars/2d7a27c79ae7a4c4d60d04e6ddc8537d.gif)
- 2020-09-29
- 1
Лемма о накачке ( лемма о разрастании , лемма-насос ; англ. pumping lemma ) — важное утверждение теории автоматов , позволяющее во многих случаях проверить, является ли данный язык автоматным . Поскольку все являются автоматными, эту проверку имеет смысл делать только для бесконечных языков. Термин «накачка» в названии леммы отражает возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка.
Существует также лемма о разрастании для контекстно-свободных языков , ещё более общее утверждение — .
Формулировка
Для бесконечного автоматного языка над алфавитом существует такое натуральное число , что для любого слова длины не меньше найдутся слова такие, что , , и для всякого неотрицательного целого цепочка является словом языка .
Запись в кванторах:
- .
Доказательство
Пусть автоматный язык содержит бесконечное число цепочек и предположим, что распознаётся детерминированным конечным автоматом с состояниями . Для проверки заключения леммы выберем произвольную цепочку этого языка, которая имеет длину .
Если конечный автомат распознаёт , то цепочка допускается этим автоматом, то есть в автомате существует путь длины из начального в одно из заключительных состояний, помеченный символами цепочки . Путь этот не может быть простым, он должен проходить ровно через состояние, в то время как автомат имеет состояний. Это значит, что этот путь проходит по меньшей мере два раза через одно и то же состояние автомата , то есть на этом пути есть цикл с повторяющимся состоянием. Пусть это повторяющееся состояние .
Разделим цепочку на три части, так что , где — подцепочка, переводящая из состояния опять в состояние , и — подцепочка, переводящая из состояния в заключительное состояние. Заметим, что как , так и могут быть пустыми, но подцепочка не может быть пустой. Но тогда очевидно, что автомат должен допускать также и цепочку , поскольку повторяющаяся подцепочка снова проходит по циклическому пути из в , а также и цепочку , и любую вида .
Это рассуждение и составляет доказательство леммы о накачке.
Обратная формулировка
Другая форма этой леммы, которую иногда удобнее применять, чтобы доказать неавтоматность некоторого языка, для языка над алфавитом состоит в следующем — если имеет место:
то язык — неавтоматный.
Для доказательства неавтоматности языка можно также пользоваться тем фактом, что пересечение регулярных языков регулярно. Так, непосредственно применить лемму о накачке к языку правильных скобочных структур в алфавите проблематично, но пересечение его с языком даёт язык , неавтоматность которого тривиально следует из леммы о накачке.
Литература
- Джон Хопкрофт , Раджив Мотвани , Джеффри Ульман . Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М. : , 2002. — С. 528. — ISBN 0-201-44124-1 .
Ссылки
- Пентус, А. Е., Пентус, М. Р. . М., 2004
- Серебряков В. А. , Галочкин М. П., Гончар Д. Р., Фуругян М. Г. — М.: МЗ-Пресс, 2006 г., 2-е изд. — ISBN 5-94073-094-9
- Винокуров Н.С. // Сиб. матем. журнал, 2005, Том 46, № 1. (недоступная ссылка с 13-05-2013 [3901 день] — )
![](https://cdn.wafarin.com/avatars/2d7a27c79ae7a4c4d60d04e6ddc8537d.gif)
- 2020-09-29
- 1