Детерминированные мп-автоматы
МП-автомат называется детерминированным, если из одной и той же его конфигурации возможно не более одного перехода в следующую конфигурацию.
Формально для детерминированного МП-автомата R(Q,V,Z,δ,q0,z0,F) функция переходов δ может VqeQ, VaeV, VzeZ иметь один из следующих трех видов:
Класс ДМП-автоматов и соответствующих им языков значительно уже, чем весь класс МП-автоматов и КС-языков. В отличие от обычного конечного автомата, не для каждого МП-автомата можно построить эквивалентный ему ДМП-авто-мат. Иными словами, в общем случае невозможно преобразовать недетерминированный МП-автомат в детерминированный.
Детерминированные МП-автоматы (ДМП-автоматы) определяют очень важный класс среди всех КС-языков, называемый детерминированными КС-языками. Доказано, что все языки, принадлежащие к классу детерминированных КС-языков, могут быть построены с помощью однозначных КС-грамматик. Поскольку однозначность — это важное и обязательное требование в грамматике любого языка программирования, ДМП-автоматы представляют особый интерес для создания компиляторов. Синтаксический распознаватель цепочек любого языка программирования может быть построен на основе ДМП-автомата.
Кроме того, доказано, что для любого ДМП-автомата всегда можно построить эквивалентный ему ДМП-автомат, который будет учитывать входную цепочку до конца — не допускать бесконечной последовательности λ-переходов по завершении цепочки [δ, т. 1]. Это значительно облегчает моделирование работы ДМП-автоматов.
Все без исключения синтаксические конструкции языков программирования задаются с помощью однозначных КС-грамматик (неоднозначность, конечно же, ни в одном компиляторе недопустима). Синтаксические структуры этих языков относятся к классу детерминированных КС-языков и могут распознаваться с помощью ДМП-автоматов. Поэтому большинство распознавателей, которые будут рассмотрены далее, относятся к классу детерминированных КС-языков.
Свойства КС-языков
Свойства произвольных КС-языков
Класс КС-языков замкнут относительно операции подстановки. Это означает, что если в каждую цепочку символов КС-языка вместо некоторого символа подставить цепочку символов из другого КС-языка, то получившаяся новая цепочка также будет принадлежать КС-языку. Это основное свойство КС-языков. Формально оно может быть записано так. Если L,Lai,La2,...,Lan — это произвольные КС-языки и {а1,а2,...,ап} — алфавит языка L, n > 0, то тогда язык L' = {х1х2...Хk| aJ1aJ2...ajkeL, xeL.,. , x2eLa.,..., xkeLa. , k>0:Vk>i>0:n>ji>0} также является КС-языком [δ, т. 1]. Например:
L = {0nln | n > 0}, l0 = {а}, L1 = (bmcm | m > 0} - это исходные КС-языки, тогда после подстановки получаем новый КС-язык: L' = {anbmicmibm2cm2...bmncmn | n > О, Vi:mi>0}.
На основе замкнутости относительно операции подстановки можно доказать другие свойства КС-языков. В частности, класс КС-языков замкнут относительно следующих четырех операций:
--- объединения;
--- конкатенации;
--- итерации;
--- гомоморфизма (изменения имен символов).
Интересно, что класс КС-языков не замкнут относительно операции пересечения, а поэтому не является классом булевой алгебры. Как следствие, этот класс не замкнут и относительно операции дополнения [δ, т. 1].
Например:
li = {апbпсi | n > 0, i > 0} и L2 = {aibncn | n > 0, i > 0} - КС-языки, но L = L1nL2 = = {anbncn | n > 0} не является КС-языком (это можно проверить с помощью леммы о разрастании КС-языков, которая рассмотрена ниже).
Для КС-языков разрешимы проблема пустоты языка и проблема принадлежности заданной цепочки языку — для их решения достаточно построить МП-автомат, распознающий данный язык. Но для КС-языков является неразрешимой проблема эквивалентности двух произвольных КС-грамматик, а, как следствие, также и проблема однозначности заданной КС-грамматики. Не разрешима даже более узкая проблема — проблема эквивалентности заданной произвольной КС-грамматики и произвольной регулярной грамматики.
Тем не менее, хотя в общем случае проблема однозначности для КС-языков не разрешима, для некоторых КС-грамматик можно построить эквивалентную им однозначную грамматику.