Математическая теория формальных языков


         

Поэтому важно иметь удобные критерии


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

Содержание  Назад  





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий