Математическая теория формальных языков
в теоретической информатике. Неудивительно, что
Цель этого курса - познакомить читателя с некоторыми основополагающими моделями и результатами, используемыми в теоретической информатике. Неудивительно, что они относятся к математике, а не к какой-либо другой области знаний - ведь в науке о компьютерах именно математические абстракции являются самыми плодотворными.
Рассматриваемые здесь идеи и результаты принадлежат теории формальных языков, грамматик и автоматов. По существу, эта теория описывает некоторые ограниченные абстрактные машины, способные выполнять определенные операции со строками. Например, конечный автомат может выяснить, содержит ли некоторый файл определенное слово, а автомат с магазинной памятью способен определить, правильна ли система вложенных круглых, квадратных и фигурных скобок.
Как подсказывает само название курса, основным объектом рассмотрения является формальный язык - произвольное множество конечных последовательностей символов, взятых из некоторого конечного множества (такие последовательности называются словами). Важность формальных языков для теоретической информатики обусловлена тем, что наиболее простой и удобной моделью данных, используемых в компьютерных программах, является конечная последовательность, каждый элемент которой взят из некоторого заранее зафиксированного конечного множества (так как для хранения этого элемента отводится фиксированный объем памяти).
В первой лекции дается классификация формальных языков в соответствии с иерархией Хомского: автоматные языки, контекстно-свободные (или бесконтекстные) языки, контекстные (или контекстно-зависимые) языки, языки типа 0. Если исключить языки, содержащие пустое слово, то названные классы вложены друг в друга (здесь они перечислены в возрастающем порядке).
В лекциях 2-6
рассматривается самый узкий из этих классов - класс автоматных (или праволинейных, или регулярных) языков, обладающий многими свойствами, важными для приложений. Например, разрешима проблема равенства автоматных языков (естественно, надо сначала договориться о способе конечного задания языка), пересечение двух автоматных языков тоже является автоматным и т.д.
Поэтому важно иметь удобные критерии автоматности, то есть условия, являющиеся одновременно необходимыми и достаточными для того, чтобы язык распознавался некоторым конечным автоматом. Наиболее известные критерии изложены в первых лекциях, их можно найти по предметному указателю (язык, автоматный, критерий автоматности). Именно автоматные языки лежат в основе лексических анализаторов, входящих в структуру компиляторов и интерпретаторов языков программирования.
В лекциях 7-11 рассматриваются контекстно-свободные языки. Изучаются разные способы выделения формального языка из множества всех слов, оказывающиеся эквивалентными друг другу в том смысле, что они задают один и тот же класс языков, а именно класс всех контекстно-свободных языков. При определении современных языков программирования (а также языков поисковых запросов и т. п.) основная часть синтаксиса описывается в формализме, известном как форма Бэкуса-Наура. По существу, это способ записывать контекстно-свободные грамматики. Другая важная область использования контекстно-свободных грамматик - расширяемый язык разметки (XML) и языки описания структуры XML-документа (например, язык DTD).
Два оставшихся класса из иерархии Хомского - контекстные языки и языки типа 0 - в данном курсе изучаются менее подробно, так как они относятся скорее к теории сложности вычислений и к теории алгоритмов соответственно. Приводятся эквивалентные определения этих классов в терминах автоматов.
Лекции 12 и 13 содержат основные результаты теории детерминированных контекстно-свободных языков и формальные определения, демонстрирующие связь этой теории с нисходящими и восходящими синтаксическими анализаторами.
Последние три лекции курса посвящены алгоритмическим проблемам, связанным с формальными грамматиками и автоматами. На основе известной из теории алгоритмов теоремы о неразрешимости проблемы Поста доказывается неразрешимость многих важных проблем теории формальных языков, например проблемы однозначности контекстно-свободной грамматики и проблемы эквивалентности двух контекстно-свободных грамматик.С другой стороны, формулируются и положительные результаты о разрешимости, в том числе теорема о разрешимости проблемы равенства детерминированных контекстно-свободных языков.
