Математическая теория формальных языков
Основные свойства контекстно-свободных языков
В лекции 2 были доказаны лемма о разрастании и свойства замкнутости класса автоматных языков. Некоторые из этих теорем имеют аналоги для класса контекстно-свободных языков (разделы 9.1 и 9.4), но этот класс не замкнут относительно дополнения и пересечения (раздел 9.5).
Лемма о разрастании для контекстно-свободных языков формализует явление "периодичности" в этих языках. Для полноты картины в разделах 9.2* и 9.3 приведены некоторые аналогичные теоремы для класса линейных языков, хотя ни в теории, ни в практических приложениях класс линейных языков значительной роли не играет.
В разделе 9.6 доказывается, что пересечение контекстно-свободного языка с автоматным языком является контекстно-свободным. В сочетании с леммой о разрастании этот факт дает удобное средство, позволяющее во многих задачах доказать, что заданный язык не является контекстно-свободным. Еще одно необходимое условие контекстной свободности сформулировано в разделе 9.7*.
