dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 60
Текст из файла (страница 60)
Либо докажите, что он соответствует определению ДМП-автомата,либо укажите правила, нарушающие его:а) МП-автомат из примера 6.2;б) (∗) МП-автомат из упражнения 6.1.1;в) МП-автомат из упражнения 6.3.3.6.4.2.Постройте ДМП-автомат для каждого из следующих языков:а) {0n1m | n ≤ m};б) {0n1m | n ≥ m};в) {0n1m0n | n и m произвольны}.Доказательство теоремы 6.19 возникает в упражнении 6.4.3, но построение P′ по P несложно.Добавим новое состояние q, в которое переходит P′, если P перешел в заключительное состояниеи следующим входным символом является $. Находясь в состоянии q, P′ выталкивает все символыиз магазина.
Кроме того, для P′ нужен дополнительный маркер дна магазина, чтобы избежать случайного опустошения магазина при имитации P.6264Стр. 264ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞ6.4.3.Теорему 6.19 можно доказать с помощью следующих трех шагов:а) докажите, что если L = N(P) для некоторого ДМП-автомата P, то L обладаетпрефиксным свойством;б) (!) докажите, что если L = N(P) для некоторого ДМП-автомата P, то существует ДМП-автомат P′, для которого L = L(P′);в) (∗!) докажите, что если L обладает префиксным свойством и L = L(P′) длянекоторого ДМП-автомата P′, то существует ДМП-автомат P, для которогоL = N(P).6.4.4.(!!) Докажите, что языкL = {0n1n | n ≥ 1} U {0n12n | n ≥ 1}является КС-языком, не допускаемым ни одним ДМП-автоматом. Указание.
Докажите, что должны существовать две цепочки вида 0n1n для различных значений n, скажем, n1 и n2, чтение которых приводит гипотетический ДМП-автоматдля языка L к одному и тому же МО. Интуитивно ДМП-автомат должен удалитьиз своего магазина почти все, что туда было помещено при чтении символов 0,для того, чтобы проверить, что далее читается равное количество символов 1.Таким образом, ДМП-автомат не может решить, следует ли допускать вход,следующий после чтения n1 или n2 символов 1.Ðåçþìå♦ Магазинные автоматы. МП-автомат — это недетерминированный конечныйавтомат с магазином, который может использоваться для запоминания цепочекпроизвольной длины.
Магазин может читаться и изменяться только со стороныего вершины.♦ Переходы магазинных автоматов. МП-автомат выбирает следующий переходна основе своего текущего состояния, следующего входного символа и символана вершине магазина. Он может также выбрать переход, не зависящий от входного символа и без его чтения. Будучи недетерминированным, МП-автомат может иметь некоторое конечное число выборов перехода; каждый из них состоитиз нового состояния и цепочки магазинных символов, заменяющей символ навершине магазина.♦ Допускание магазинными автоматами. Существуют два способа, которыми МПавтомат может сигнализировать допуск.
Один заключается в достижении заключительного состояния, другой — в опустошении магазина. Эти способы эквивалентны в том смысле, что любой язык, допускаемый по одному способу, допускается и по другому (некоторым другим МП-автоматом).ÐÅÇÞÌÅСтр. 265265♦ Мгновенные описания (МО), или конфигурации. Для описания “текущего положения” МП-автомата используется МО, образуемое состоянием, оставшимся входоми содержимым магазина. Отношение переходов |− между МО представляет отдельные переходы МП-автомата.♦ Магазинные автоматы и грамматики.
Класс языков, допускаемых МП-автоматами как по заключительному состоянию, так и по пустому магазину, совпадаетс классом КС-языков.♦ Детерминированные магазинные автоматы. МП-автомат является детерминированным, если у него никогда нет выбора перехода для данных состояния, входногосимвола (включая ε) и магазинного символа. У него также нет выбора между переходом с использованием входного символа и переходом без его использования.♦ Допускание детерминированными магазинными автоматами. Два способа допускания — по заключительному состоянию и по пустому магазину — неэквивалентны для детерминированных МП-автоматов. Точнее, языки, допускаемые попустому магазину, — это те, и только те, языки, которые допускаются по заключительному состоянию и обладают префиксным свойством (ни одна цепочка языка не является префиксом другой).♦ Языки, допускаемые ДМП-автоматами.
Все регулярные языки допускаются (позаключительному состоянию) ДМП-автоматами, и существуют нерегулярные языки, допускаемые ДМП-автоматами. Языки ДМП-автоматов являются контекстносвободными, причем для них существуют однозначные грамматики. Таким образом, языки ДМП-автоматов лежат строго между регулярными и контекстносвободными языками.ËèòåðàòóðàИдея магазинного автомата была высказана независимо в работах Эттингера [4] и Шютценберже [5]. Установление эквивалентности магазинных автоматов и контекстно-свободныхграмматик также явилось результатом независимых исследований; оно было представленоХомским в техническом отчете MIT за 1961 г., но впервые было опубликовано в [1].Детерминированный МП-автомат впервые был предложен Фишером [2] и Шютценберже [5].
Позднее он приобрел большое значение как модель синтаксического анализатора. Примечательно, что Кнут предложил в [3] “LR(k)-грамматики”, подкласс КСграмматик, порождающих в точности языки ДМП-автоматов. LR(k)-грамматики, в своюочередь, образуют базис для YACC, инструмента для создания анализаторов, обсуждаемого в разделе 5.3.2.1.266Стр. 266J. Evey, “Application of pushdown store machines,” Proc. Fall Joint Computer Conference (1963), AFIPS Press, Montvale, NJ, pp.
215–227.ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞ2.P. C. Fischer, “On computabililty by certain classes of restricted Turing machines,”Proc. Fourth Annl. Symposium on Switching Circuit Theory and Logical Design (1963),pp. 23–32.3.D. E. Knuth, “On the translation of languages from left to right,” Information and Control8:6 (1965), pp. 607–639. (Кнут Д. О переводе (трансляции) языков слева направо.
—Сб. “Языки и автоматы”. — М.: Мир, 1975. — С. 9–42.)4.A. G. Oettinger, “Automatic syntactic analysis and pushdown store,” Proc. Symposia onApplied Math. 12 (1961), American Mathematical Society, Providence, RI.5.M. P. Schutzenberger, “On context-free languages and pushdown automata,” Informationand Control 6:3 (1963), pp. 246–264.ËÈÒÅÐÀÒÓÐÀСтр. 267267268Стр. 268ÃËÀÂÀ 6. ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞÃËÀÂÀ 7Ñâîéñòâàêîíòåêñòíîñâîáîäíûõ ÿçûêîâНаше изучение контекстно-свободных языков завершается знакомством с некоторыми изих свойств. Вначале определяются ограничения на структуру продукций КС-грамматик идоказывается, что всякий КС-язык имеет грамматику специального вида.
Этот факт облегчает доказательство утверждений о КС-языках.Затем доказывается “лемма о накачке” для КС-языков. Эта теорема аналогична теореме 4.1 для регулярных языков, но может быть использована для доказательства того,что некоторые языки не являются контекстно-свободными. Далее рассматриваютсясвойства, изученные в главе 4 для регулярных языков, — свойства замкнутости и разрешимости. Показывается, что некоторые, но не все, свойства замкнутости регулярныхязыков сохраняются и у КС-языков. Часть задач, связанных с КС-языками, разрешается спомощью обобщения проверок, построенных для регулярных языков, но есть и ряд вопросов о КС-языках, на которые нельзя дать ответ.7.1. Íîðìàëüíûå ôîðìû êîíòåêñòíî-ñâîáîäíûõãðàììàòèêЦель этого раздела — показать, что каждый КС-язык (без ε) порождается грамматикой,все продукции которой имеют форму A → BC или A → a, где A, B и C — переменные, a —терминал. Эта форма называется нормальной формой Хомского.
Для ее получения нужнонесколько предварительных преобразований, имеющих самостоятельное значение.1.Удалить бесполезные символы, т.е. переменные или терминалы, которые не встречаются в порождениях терминальных цепочек из стартового символа.2.Удалить ε-продукции, т.е. продукции вида A → ε для некоторой переменной A.3.Удалить цепные продукции вида A → B с переменными A и B.7.1.1.
Óäàëåíèå áåñïîëåçíûõ ñèìâîëîâСимвол X называется полезным в грамматике G = (V, T, P, S), если существует неко**торое порождение вида S ⇒ αXβ ⇒ w, где w ∈ T*. Отметим, что X может быть как переменной, так и терминалом, а выводимая цепочка αXβ — первой или последней в по-Стр. 269рождении. Если символ X не является полезным, то называется бесполезным. Очевидно,что исключение бесполезных символов из грамматики не изменяет порождаемого языка,поэтому все бесполезные символы можно обнаружить и удалить.Наш подход к удалению бесполезных символов начинается с определения двухсвойств, присущих полезным символам.*1.Символ X называется порождающим, если X ⇒ w для некоторой терминальной цепочки w. Заметим, что каждый терминал является порождающим, поскольку w может быть этим терминалом, порождаемым за 0 шагов.2.Символ X называется достижимым, если существует порождение S ⇒ αXβ для не-*которых α и β.Естественно, что полезный символ является одновременно и порождающим, и достижимым.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
