Математическая теория формальных языков
Основные свойства автоматных языков
Для практического применения теории конечных автоматов нужны средства, позволяющие выяснять, является ли некоторый формальный язык автоматным. Для получения положительного ответа на такой вопрос могут пригодиться достаточные условия автоматности, для отрицательного ответа - необходимые условия автоматности. В этой лекции рассматриваются наиболее часто используемые условия, касающиеся автоматности формального языка.
В первых двух разделах этой лекции доказываются свойства замкнутости класса всех автоматных языков (относительно итерации, конкатенации, объединения, дополнения, пересечения и т. д.). Эти свойства можно использовать как достаточные условия автоматности. Например, если нужно выяснить, является ли язык L автоматным, и удается представить L в виде , где языки L1 и L2
автоматные, то и язык L обязательно является автоматным.
В последних двух разделах этой лекции доказывается так называемая лемма о разрастании (в англоязычной литературе pumping lemma), которая во многих случаях позволяет установить неавтоматность формального языка. К сожалению, эта лемма помогает не всегда, так как дает всего лишь необходимое условие, а не критерий автоматности.
