Автоматы с магазинной памятью

Автоматы с магазинной памятью АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во многих случаях можно рассматри­вать как бесконтекстные. В отличие от конечных , На рис. 1 такой преобразователь. Конечное управляющее устройство снабжается дополнительной управляющей головкой, всегда указывающей на 1) стереть символ из верхней ячейки (при этом все символы, находящиеся на рабочей ленте, перемещаются на одну ячейку вверх); 2) стереть символ из верхней ячейки и записать на рабочую ленту непустую цепочку символов (при этом содержимое рабочей ленты сдвигается вниз ровно настолько, какова длина Таким образом, устройство магазинной памяти можно сравнить с устройством магазина боевого автомата: когда в него вкладывается патрон, те, которые уже были внутри, проталкиваются вниз; до­стать можно только патрон, вложенный последним. Формально детерминированный магазинный автомат M = (V, Q, VM , δ, q00 , F), 0 Є VM 0 , z1 ,…,zp -1 } — алфавит магазинных символов авто­мата; δ — функция, отображающая множество Q X ( V U { ε }) X VM в множество Q X VM z0 Є VM — так называемый граничный маркер, т. е. символ, Недетерминированный магазинный автоматδ отображает множество Q X ( V U { ε }) X VM . в множество конечных подмножеств Q x VM Как и в случае конечных автоматов, преобразователи с магазинной памятью отличаются от автоматов с магазинной памятью нали­чием выходной ленты. Далее будем рассматривать только недетерминированные магазин­ные автоматы. Рассмотрим интерпретацию функции δ для такого автомата. Эту функцию можно представить совокупностью команд вида →(q1 , γ1 ),…,(qm , γm ), гдеq, q1 ,…qm Є Q, a Є V, z Є VMγ1γm* m При этом считается, что если на входе читающей головки авто­ мата находится символ а , автомат находится в состоянии q , а верхний символ рабочей ленты z , то автомат может перейти к состоянию qi γi≤ i ≤ m) вместо символа z , передвинуть входную головку на один символ вправо так, как это показано на рис. 1, и перейти в состояние qi . Крайний левый символ γi должен при этом оказаться в верхней ( q , e , z )→( q 1 , γ 1 ),…, ( qm , γm ) означает, что независимо от входного символа и, не передвигая входной го- + ловки, автомат перейдет в состояние qi z магазина на цепочку γi (1 ≤ i ≤ m ). • Ситуацией магазинного автомата называется пара ( q , γ ) , где q Є Q , γ Є V * m . Между ситуациями магазинного автомата ( q , γ ) и ( q ’, γ ’)├, если среди команд найдется такая, что →(q1 , γ1 ),…,(qmγm ), причемγ= zβ, γ’ = γi β q ' = qi длянекоторого≤ i ≤ m (z Є Vm , β Є V* m Говорят, что магазинный автомат переходит из состояния ( q , γ ) в состояние ( q ’, γ ’) и обозначают это следующим образом: a: (q, γ)├ (q’, γ’) . Вводится и такое обозначение: a1n : (q, γ)├ * (q’, γ’), ai : (qiγi├ (qi+1 , γi+1 ), 1 ≤ i ≤ m где ai Є V , γ 1 = γ , γ 2 ,…, γn +1 = γ ’ Є V * m q 1 = q , q 2 ,…, qn +1 = q ’ Є Q Существует два способа определения языка, допускаемого ма­газинным автоматом. Согласно первому способу считается, что входная цепочка α Є V *L 1 ( M ) в магазине автомата М будет находиться пустая цепочка ε . Другими словами, L1 (M) = { α α : (q0 , z0├ * (q, ε )} где q Є Q . Согласно второму способу считается, что входная цепочка при­надлежит языку L 2 ( M ) тогда, когда после просмотра последнего символа, входящего в эту цепочку, автомат М окажется в одном из своих заключительных состояний q f Є F . Другими словами, L 2 ( M α α: ( q 0 , z 0 ) ├ * ( qf , γ )} где γ Є V * m , qf Є F Доказано, что множество языков, допускаемых произвольными магазинными автоматами согласно первому способу, совпадает с множеством языков, допускаемых согласно второму способу. Доказано также, что если L ( G 2 ) — бесконтекстный язык, по­рождаемый Грамматикой G2 = ( Vx , VT , Р, S ) , являющейся нормаль­ной формой Грейбах, произвольной бесконтекстной грамматики G , то существует недетерминированный магазинный автомат М такой, что L 1 ( M ) = L ( G 2 ). При этом M = (V, Q, Vm , δ, q0 , z0 ГдеV=VT0M =VN ; z0 =S а для каждого правила G 2 вида A→a α , a Є VT , a Є V* n строится команда отображения δ : (q0 , a, A)→(q0 , a) М , допускающего язык L 1 ( M ) , можно построить бескон­текстную грамматику GL ( G ) = L 1 ( M ). Если для конечных автоматов детерминированные и недетерми­нированные модели эквивалентны по отношению к классу допускае­мых языков, то этого нельзя сказать для магазинных автоматов. Детерминированные автоматы с магазинной памятью допускают лишь некоторое подмножество бесконтекстных языков, которые называют детерминированными бесконтекстными языками. Список использованной литературы КУЗИН Л. Т «Основы кибернетики» Т. 2 ХИМИКО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ Р Е Ф Е Р А Т По дискретной математике на тему: «Автоматы с магазинной памятью» Подготовил Кирчатов Роман Романович Преподаватель Бразинская Светлана Викторовна ДНЕПРОПЕТРОВСК, 2002