Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 60
Текст из файла (страница 60)
Он должен проверить, что после 11 находятся и символов О, и для этого он должен опустошить свой магазив.' Теперь он прочитал 0" 110". Если далее он видит идентичную цепочку, он должен допускать, поскольку весь вход имеет вид ичг, где и = 0"110". Однако если Р видит 0 110, ще м е и, он должен не допускать. Поскольку его магазин пуст, он не может запомнить, юким было произвольное целое л, и не способен допустить Е„„, Подведем итог.
° Языки, допускаемые ДМП-автоматами по заключительному состоянию, включают регулярные языки как собственное подмножество, но сами образуют собственное подмножество КС-языков. (ь4.4. Детерминированные й4П-автоматы и неоднозначные грамматики Мощность ДМП-автоматов можно уточнить, заметив, что все языки, допускаемые вив, имеют однозначные грамматики. К сожалению, класс языков ДМП-автоматов не совпадает с подмножеством КС-язь1ков, не являющихся существенно неоднозначными.
Например, („,„., имеет однозначную грамматику о — э 050 ~ 1511е, хотя и не является ДМП-автоматным языком. Следующая теорема уточняет заключительное утверждение ю подраздела 6.4,3. Теорема 6.20. Если Т, = Д?(Р) для некоторого ДМП-автомата Р, то Т, имеет однозначную КС-грамматику. Доказательство. Утверждаем, что конструкция теоремы 6.14 порождает однозначвую КС-грамматику С, когда МП-автомат, к которому она применяется, детерминиромв. Вначале вспомним (см.
теорему 5.29), что для однозначности грамматики б достаючно показать, что она имеет уникальные левые порождения. Предположим, Р допускает ж по пустому магазину. Тогда он делает это с помощью одной-единственной последовательности переходов, поскольку он детерминирован и не нижет работать после опустошения магазина. Зная эту последовательность переходов, мн можем однозначно определить выбор каждой продукции в левом порождении ж в б. Правило автомата Р, на основании которою применяется продукция, всегда одно. Но правило, скажем, 4д, а, л) = ((г, Г, Уэ.,. Гг)), может порождать много продукций грамматики 6, с различными состояниями в позициях, отражающих состояния Р после удаления аждого из Уь 1ь ..., Уь Однако, поскольку Р детерминирован, осуществляется только одна из этих последовательностей переходов, поэтому только одна из этих продукций в действительности ведет к порождению в.
П Мы можем, однако, доказать больше: даже языки, допускаемые ДМП-автоматами по мключительному состоянию, имеют однозначные грамматики. Поскольку мы знаем ' Это интуитивное утверждение требует сложною формального доказательства; возможен ли другой способ для Р сравнить лва равных блока символов О? 6.4.
ДЕТЕРМИНИРОВАННЫЕ АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 263 лишь, как строятся грамматики, исходя из МП-автоматов, допускающих по пустому магазину, нам придется изменять язык, чтобы он обладал префиксным свойством, а затем модифицировать грамматику, чтобы она порождала исходный язык. Обеспечим это с помощью "концевого маркера'.
Теорема 6.21. Если Е = Е(Р) для некоторого ДМП-автомата Р, то Е имеет однозначную КС-грамматику. Доказательство. Пусть $ будет "концевым маркером", отсутствующим в цепочках языка Е, и пусть Е'= Еб. Таким образом, цепочки языка Е' представляют собой цепочки из Е, к которым дописан символ б. Тогда Е' имеет префиксное свойство, и по теореме 6.19 Е'= Лг(Р') для некоторого ДМП-автомата РСл По теореме 6.20 существует однозначная грамматика С; порождающая язык 1т(Р~, т.е. Е( Теперь по грамматике С'построим С, для которой ЦС) = Е.
Для этого нужно лишь избавиться от маркера 3 в цепочках. Будем рассматривать э как переменную грамматики С н введем продукцию 5 — з е; остальные продукции С и С' одинаковы. Поскольку Е(С') = Е', получаем, что ЦС) = Е. Утверждаем, что С однозначна, Действительно, левые порождения в С совпадают с левыми порождениями в С; за исключением последнего шага в С вЂ” изменения э на ж Таким образом, если бы терминальная цепочка ш имела два левых порождения в С, то шэ имела бы два порождения в С'.
Поскольку С'однозначна, С также однозначна. Е) 6.4.5. Упражнения к разделу 6.4 6.4.1. Для каждого из следующих МП-автоматов укажите, является ли он детерминированным. Либо докажите, что он соответствует определению ДМП-автомата, либо укажите правила, нарушающие его: а) МП-автомат из примера 6.2; б) (е) МП-автомат из упражнения 6.1.1; в) МП-автомат из упражнения 6.3.3. 6.4.2. Постройте ДМП-автомат для каждого из следующих языков: а) (01 (п<зл); б) (0" 1 ) и > гн ); в) (О" 1"0") иняз произвольны). Доказательство теоремы 6.19 возникает в упражнении 6.4.3, но построение Р' по Р несложно.
Добавим новое состояние 9, в которое переходит Р; если Р перешел в заключительное состояние и следующим входным символом является 5. Нахолясь в состоянии д, Р'выталкивает асе символы из магазина. Кроме того, для Р'нужен дополнительный маркер дна магазина, чтобы избежать случайного опустошения магазина при имитации Р. ГЛАВА 6. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 264 , (ь4.3.
Теорему 6.19 можно доказать с помощью следующих трех шагов: а) докажите, что если Ь = Х(Р) для некоторого ДМП-автомата Р, то Ь обладает префиксным свойством; б) (1) докажите, что если Ь = М(Р) для некоторого ДМ11-автомата Р, то существует ДМП-автомат Р; для которого Ь =- Ь(Р'~; в) (э1) докажите, что если Ь обладает префиксным свойством и Ь = Ь(Р) для некоторого ДМП-автомата Р; то существует ДМП-автомат Р, для которого Ь= Н(Р), 6.4.4.
(11) Докажите, что язык Ь= (О"1')н> 1) () (О"1 "(л~!) является КС-языком, не допускаемым ни одним ДМП-автоматом. Указание. Докажите, что должны существовать две цепочки вида О" 1" для различных значений и, скажем, н~ и пл чтение которых приводит гипотетический ДМП-автомат для языка Ь к одному и тому же МО. Интуитивно ДМП-автомат должен удалить из своего магазина почти все, что туда было помеьдено при чтении символов О, для того, чтобы проверить, что далее читается равное количество символов 1.
Таким образом, ДМП-автомат не может решить, следует ли допускать вход, следующий после чтения и, или кц символов 1. Резюме в Магазинные автоматы. МП-автомат — зто недетерминированный конечный автомат с магазином, который может использоваться для запоминания цепочек произвольной длины. Магазин может читаться и изменяться только со стороны его вершины.
я Переходы магазинных автоматов. МП-автомат выбирает следующий переход на основе своего текущего состояния, следующего входного символа и символа на вершине магазина. Он может также выбрать переход, не зависящий от входного символа и без его чтения. Будучи недетерминированным, МП-автомат может иметь некоторое конечное число выборов перехода; каждый из них состоит из нового состояния и цепочки магазинных символов, заменяющей символ на вершине магазина. в Долускаяие магизияпыми автоматами. Существуют два способа, которыми МП- автомат может сигнализировать допуск. Один заключается в достижении заключительного состояния, другой — в опустошении магазина. Эти способы эквивалентны в том смысле, что любой язык, допускаемый по одному способу, допускается и по другому (некоторым другим МП-автоматом).
РЕЗЮМЕ 265 + Мгновенные описании [МО), или конфигурации. Для описания "текущего положения" МП-автомата используется МО, образуемое состоянием, оставшимся входом и содержимым магазина. Отношение переходов ]- между МО представляет от- дельные переходы МП-автомата. е ЛГагазинные автоматы и грамматики. Класс языков, допускаемых МП-авто- матами как по заключительному состоянию, так и по пустому магазину, совпадает с классом КС-языков. + Детерминированные магазинные автоматы. МП-автомат является детерминированным, если у него никогда нет выбора перехода для данных состояния, входного символа [включая в) и магазинного символа, У него также нет выбора между переходом с использованием входного символа и переходом без его использования.
е Допускание детерминированнымн тагазштыми автоматами. Два способа до- пускания — по заключительному состоянию и по пустому магазину — неэквивалентны для детерминированных МП-автоматов. Точнее, языки, допускаемые по пустому магазину, — это те, и только те, языки, которые допускаются по заключительному состоянию и обладают префиксным свойством (ни одна цепочка языка не является префиксом другой). е Языки, допускаемые ДМП-автоматами.
Все регулярные языки допускаются (по заключительному состоянию) ДМП-автоматами, и существуют нерегулярные языки, допускаемые ДМП-автоматами. Языки ДМП-автоматов являются контекстносвободиыми, причем для них существуют однозначные грамматики. Таким образом, языки ДМП-автоматов лежат строго между регулярными и контекстно- свободными языками. Литература Идея магазинного автомата была высказана независимо в работах Эттингера [4) и Шютценберже [5]. Установление эквивалентности магазинных автоматов и контекстно-свободных грамматик также явилось результатом независимых исследований; оно было представлено Хомским в техническом отчете МГГ за 1961 г., но впервые было опубликовано в [1]. Детерминированный МП-автомат впервые был предложен Фишером [2] и Шютценберже [5]. Позднее он приобрел большое значение как модель синтаксического анализатора.
Примечательно, что Кнут прелложил в [3] "1.К[Л)-грамматики", подкласс КС- грамматик, порождающих в точности языки ДМП-автоматов. 1.и(Л)-грамматики, в свою очередь, образуют базис для УАСС, инструмента для создания анализаторов, обсуждаемого в разделе 5.3.2.. 1, 1. Ечеу, "Арр!гсабоп оГ роз[к!ознп з!оге шасМпез," Ргос. Рай уоип Сотршег Соп[вгепсе (1963), АР]РЗ Ргезз, Мопгуа!е, )91, рр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
