dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 53
Текст из файла (страница 53)
Aho, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools,Addison-Wesley, Reading MA, 1986. (Ахо А. В., Сети Р., Ульман Дж. Компиляторы:принципы, технологии и инструменты. — М.: Издательский дом “Вильямс”, 2001.)2.J. W. Backus, “The syntax and semantics of the proposed international algebraic languageof the Zurich ACM-GAMM conference”, Proc.
Intl. Conf. on Information Processing(1959), UNESCO, pp. 125–132.3.D. C. Cantor, “On the ambiguity problem of Backus systems”, J. ACM 9:4 (1962),pp. 477–479.4.N. Chomsky, “Three models for the description of language”, IRE Trans. on InformationTheory 2:3 (1956), pp. 113–124.
(Хомский Н. Три модели для описания языка. — Кибернетический сборник, вып. 2. — М.: ИЛ, 1961. — С. 237–266.)5.R. W. Floyd, “On ambiguity in phrase-structure languages”, Comm. ACM 5:10 (1962),pp. 526–534.6.M. Gross, “Inherent ambiguity of minimal linear grammars”, Information and Control 7:3(1964), pp. 366–368.7.P. Naur et al., “Report on the algorithmic language ALGOL 60”, Comm.
ACM 3:5 (1960),pp. 299-314. См. также Comm. ACM 6:1 (1963), pp. 1–17. (Алгоритмический язык Алгол 60. — М.: Мир, 1965.)8.World-Wide-Web Consortium, http://www.w3.org/TR/REC-xml (1998).ËÈÒÅÐÀÒÓÐÀСтр. 231231232Стр. 232ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈÃËÀÂÀ 6Àâòîìàòûñ ìàãàçèííîéïàìÿòüþКонтекстно-свободные языки задаются автоматами определенного типа. Такой автоматназывается автоматом с магазинной памятью, или магазинным автоматом, и являетсярасширением недетерминированного конечного автомата с ε-переходами, представляющего собой один из способов определения регулярных языков.
Магазинный автомат —это, по существу, ε-НКА с добавлением магазина. Магазин может читаться, в его вершину могут добавляться (заталкиваться, помещаться, заноситься) или с его вершины могутсниматься символы точно так же, как в структуре данных типа “магазин”.В этой главе определяются две различные версии магазинных автоматов: одна из нихдопускает при достижении допускающего состояния, как это делают конечные автоматы,а другая — при опустошении магазина независимо от состояния. Показывается, что этидва варианта допускают контекстно-свободные языки, т.е. грамматики могут быть преобразованы в эквивалентные магазинные автоматы, и наоборот. Также вкратце рассматривается подкласс детерминированных магазинных автоматов.
Множество допускаемыхими языков включает все регулярные языки, но является собственным подмножествомКС-языков. Поскольку механизмом своей работы они весьма похожи на синтаксическиеанализаторы, важно знать, какие языковые конструкции могут быть распознаны ими, акакие — нет.6.1. Îïðåäåëåíèå àâòîìàòîâ ñ ìàãàçèííîé ïàìÿòüþВ этом разделе магазинный автомат представлен сначала неформально, а затем — какформальная конструкция.6.1.1. Íåôîðìàëüíîå ââåäåíèåМагазинный автомат — это, по существу, недетерминированный конечный автомат сε-переходами и одним дополнением — магазином, в котором хранится цепочка“магазинных символов”.
Присутствие магазина означает, что в отличие от конечного автомата магазинный автомат может “помнить” бесконечное количество информации. Однако в отличие от универсального компьютера, который также способен запоминать неограниченные объемы информации, магазинный автомат имеет доступ к информации вСтр. 233магазине только с одного его конца в соответствии с принципом “последним пришел —первым ушел” (“last-in-first-out”).Вследствие этого существуют языки, распознаваемые некоторой программой компьютера и нераспознаваемые ни одним магазинным автоматом. В действительности, магазинные автоматы распознают в точности КС-языки.
Многие языки контекстно-свободны,включая, как мы видели, некоторые нерегулярные, однако существуют языки, которыепросто описываются, но не являются контекстно-свободными. Мы увидим это в разделе 7.2. Примером такого языка является {0n1n2n | n ≥ 1}, т.е. множество цепочек, состоящих из одинаковых групп символов 0, 1 и 2.ВходКонечноеуправлениеДопустить/отвергнутьМагазинРис. 6.1. Магазинный автомат как конечный автомат с магазинной структурой данныхМагазинный автомат можно рассматривать неформально как устройство, представленное на рис.
6.1. “Конечное управление” читает входные символы по одному. Магазинный автомат может обозревать символ на вершине магазина и совершать переход наоснове текущего состояния, входного символа и символа на вершине магазина. Он может также выполнить “спонтанный” переход, используя ε в качестве входного символа.За один переход автомат совершает следующие действия.1.Прочитывает и пропускает входной символ, используемый при переходе.
Если в качестве входа используется ε, то входные символы не пропускаются.2.Переходит в новое состояние, которое может и не отличаться от предыдущего.3.Заменяет символ на вершине магазина некоторой цепочкой. Цепочкой может быть ε,что соответствует снятию с вершины магазина.
Это может быть тот же символ, который был ранее на вершине магазина, т.е. магазин не изменяется. Автомат можетзаменить магазинный символ, что равносильно изменению вершины без снятий и заталкиваний. Наконец, символ может быть заменен несколькими символами — эторавносильно тому, что (возможно) изменяется символ на вершине, а затем туда помещаются один или несколько новых символов.Пример 6.1. Рассмотрим язык Lwwr = {wwR | w ∈ (0 + 1)*}. Этот язык образован палиндромами четной длины над алфавитом {0, 1} и порождается КС-грамматикой (см.рис. 5.1) с исключенными продукциями P → 0 и P → 1.234Стр. 234ÃËÀÂÀ 6.
ÀÂÒÎÌÀÒÛ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞДадим следующие неформальное описание магазинного автомата, допускающегоLwwr.11.Работа начинается в состоянии q0, представляющем “догадку”, что не достигнута середина входного слова, т.е. конец слова w, за которым должно следовать его отражение.В состоянии q0 символы читаются и их копии по очереди записываются в магазин.2.В любой момент можно предположить, что достигнута середина входа, т.е. конецслова w. В этот момент слово w находится в магазине: левый конец слова на дне магазина, а правый — на вершине. Этот выбор отмечается спонтанным переходом всостояние q1.
Поскольку автомат недетерминирован, в действительности предполагаются обе возможности, т.е. что достигнут конец слова w, но можно оставаться всостоянии q0 и продолжать читать входные символы и записывать их в магазин.3.В состоянии q1 входные символы сравниваются с символами на вершине магазина.Если они совпадают, то входной символ пропускается, магазинный удаляется, и работа продолжается.
Если же они не совпадают, то предположение о середине слованеверно, т.е. за предполагаемым w не следует wR. Эта ветвь вычислений отбрасывается, хотя другие могут продолжаться и вести к тому, что цепочка допускается.4.Если магазин опустошается, то действительно обнаружен вход w, за которым следует wR. Прочитанный к этому моменту вход допускается.6.1.2.
Ôîðìàëüíîå îïðåäåëåíèå àâòîìàòà ñ ìàãàçèííîé ïàìÿòüþФормальная запись магазинного автомата (МП-автомата) содержит семь компонентов и выглядит следующим образом.P = (Q, Σ, Γ, δ, q0, Z0, F)Компоненты имеют такой смысл.Q: конечное множество состояний, как и у конечного автомата.Σ: конечное множество входных символов, такое же, как у конечного автомата.Γ: конечный магазинный алфавит. Он не имеет конечноавтоматного аналога и является множеством символов, которые можно помещать в магазин.δ: функция переходов. Как и у конечных автоматов, δ управляет поведением автомата.
Формально, аргументами δ являются тройки δ(q, a, X), в которых q — состояниеиз множества Q, a — либо входной символ, либо пустая цепочка ε, которая, по пред-1Можно было бы также построить магазинный автомат для Lpal, языка, грамматика которогопредставлена на рис. 5.1. Однако Lwwr несколько проще и позволит нам сосредоточиться на идеях,касающихся магазинных автоматов.6.1. ÎÏÐÅÄÅËÅÍÈÅ ÀÂÒÎÌÀÒÎÂ Ñ ÌÀÃÀÇÈÍÍÎÉ ÏÀÌßÒÜÞСтр. 235235положению, не принадлежит входному алфавиту, X — магазинный символ из Γ. Выход δ образуют пары (p, γ), где p — новое состояние, а γ — цепочка магазинныхсимволов, замещающая X на вершине магазина. Например, если γ = ε, то магазинныйсимвол снимается, если γ = X, то магазин не изменяется, а если γ = YZ, то X заменяется на Z, и Y помещается в магазин.q0: начальное состояние. МП-автомат находится в нем перед началом работы.Z0: начальный магазинный символ (“маркер дна”).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
