Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 56
Текст из файла (страница 56)
АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 244 Доказательство. Идея доказательства представлена иа рис. 6,4. Используется новый символ Х,, который ие должен быть элементом Г; Х, является как стартовым символом автомата Рм так и маркером диа магазина, позволяющим узнать, когда Рн опустошает магазин. Таким образом, если Ру обозревает Х, иа вершине магазина, то ои знает, что Рм опустошает свой магазин иа этом же входе, е, Хе / е Нач е,Хе/е Рис.
б.4. Ре имитирует Рч и допускает, если Ри опустошает свой магазин Нам нужно также новое начальное состояиие рв, единственной функцией которого является затолкнуть 2„стартовый символ автомата Рч, иа вершину магазина и перейти в состояние Ч,, начальное для Рн. Далее Рн имитирует Рн до тех пор, пока магазин Ри ие станет пустым, что Рн определяет по символу Хе иа вершине своего магазина. И наконец, нужно еще одно новое состояние Рд заключительное в автомате Р,й ои переходит в рл как только обнаруживает, что Рн опустошает свой магазин. Описание Рн имеет следующий вид.
Рг=И()(Р,Ру), ь, ГО (Хв), б;,Рв,Хв, (Р)) Функция бн определяется таким образом. й бн(рр, е,Хв) = [(с)„УвХв)). В своем начальном состоянии Рн спонтанно переходит в начальное состояние автомата Рм заталкивая его стартовый символ ев в магазии.
2. Для всех состояний с( из Д, входов а из Х (или а = 6) и магазинных символов )' из Г, бл(д, а, у) содержит все пары из бл( у, а, У). 3. В дополнение к правилу (2), бн(г(, е, Х,) содержит (р; 6) для каждого состояния д из Д. Докажем, что ш и ).(Рн) тогда и только тогда, когда ш и зз(Рн). (Достаточность) Нам дано, что (гув, и, 7в) )- (д, к, 6) для некоторого состояния с). По теореме 6.5 можно добавить Х„иа дио магазина и заключить, что (зв, ш, УвХв) ~- (Ф е, Хе). Поскольку по правилу 2 у Рн есть все переходы Рм можно утверждать также, 6.2. ЯЗЫКИ МП-АВТОМАТОВ 245 что (др, ич ДХр) (- (д, б, Х,).
Если эту последовательность переходов собрать вместе с Р, начальным и заключительным переходами в соответствии с правилами 1 и 3, то получим следуюшее. (рр, чр,Хр) ~- (Лр,чр,срХр) 'Г- (е1, б,Хр) 1- (рд б, б) (6.1) Таким образом, Ри допускает чр по заключительному состоянию. (Необходинасрль) Заметим, что дополнительные переходы по правилам 1 и 3 дают весьма ограниченные возможности для допускания и по заключительному состоянию.
Правило 3 должно использоваться только на последнем шаге, и его можно использовать, если магазин Ре содержит лишь Х,. Но Х, не появляется нигде в магазине, кроме его дна. Правило 1 используется только на первом шаге, и оно доллсио использоваться на первом шаге. Таким образом, любое вычисление в автомате Рт допускающее и, должно выглядеть как последовательность (6.1). Более того, середина вычисления (все переходы, кроме первого и последнего) должна также быть вычислением в Ри с Х, под магазином, Это обусловлено тем, что, за исключением первого и последнего шагов, Рк не может использовать переходы, которые не являются переходами Рт и Хр не может оказаться на вершине магазина (иначе вычисление заканчивалось бы на следующем шаге).
Таким обра- зом, (е)р, и', 7р) ~- (р1, б, б), и и'е гч(Ри). П Примерб.!О.Построим МП-автомат, который обрабатывает последовательности слов 16 и е1ве в С-программе, где 1 обозначает Гй, а е — е1ве. Как показано в разделе 5.3.1, в любом префиксе программы количество е1ве не может превышать числа 1й, поскольку в противном случае слову е1ве нельзя сопоставить предшествуюшее ему 1Т. Итак, магазинный символ а используется для подсчета разницы между текушими количествами просмотренных 1 и е. Этот простой МП-автомат с единственным состоянием представлен диаграммой переходов на рис. 6.5.
Н 2/22 Начало Ч Рис. 6.5. МП-артомат, допускающий ошибки Кlе1ле ло лустому масарику Увидев г, автомат заталкивает х, а е — выталкивает. Поскольку он начинает с одним х в магазине, в действительности он следует правилу, что если в магазине 2", то символов 1 прочитано на и — 1 больше, чем е. В частности, если магазин пуст, то символов е прочитано на один больше, чем б и входная последовательность недопустима в С-прог- ГЛАВА 6.
АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 246 раиме. Именно такие цепочки наш МП-автомат Рн допускает по пустому магазину. Его формзльное определение имеет следующий вид. Рн= ((с)), (з, е), (с), Бм д, 2) Функция Бн задается таким образом. 1. бн(д, б У) = ((с), УУ)). По этому правилу заталкивается 2 при з' на входе, 2. бн(з), е, Д = ((д, 2)). У выталкивается при входе е. в,2/в З, 2З22 Рис б.б.
Конструкьчт ЧЛ-автомата, допускаюисего по заключительному состоянию и построенного на основе автомата Ри (см. рис. б.5) Теперь на основе Рн построим МП-автомат Рт допускающий этот же язык по заклююпельному состоянию; его диаграмма переходов показана на рис. б.б. Вводим новые з начальное и заключительное состояния р и г, а также используем Х, в качестве маркера лна магазина. Формально автомат Рк определяется следующим образом.
Рг = ((р, ч, г), (ю', е), (2, Хв) бт з), ~) Функция Бу задается таким образом. й Бг(р, к Хв) = ((д, УХв)). По этому правилу Ру начинает имитировать Рн с маркером дна магазина. 2. бг(о, ~', У) = ((с(, У2)). Узаталкивается при входе з, как у Рм 3. б(с), е, 2) = ((д, 2)). Увыталкнвается при входе в, как у Рн. бр(з), в, Хв) = ((г, е)). Рг допускает, когда имитируемый Ркопустошает свой магазин.
6.2.4. От заключительного состояния к пустому магазину Теперь пойдем в обратном направлении: исходя из МП-автомата Ри; допускающего язык Е по заключительному состоянию, построим другой МП-автомат Рн, который допускает Е по пустому магазину. Конструкция проста и представлена на рис. 6.7. Добавляется переход по 6 из каждого допускающего состояния автомата Рк в новое состояние р. Находясь в состоянии р, Рн опустошает магазин и ничего не прочитывает на входе. ' Не обрашайте внимания на то, что тут использованы новые состояния р н г, хотя в конструкции теоремы 6.9 указаны рв и,о,. Имена состояний могут быть совершенно произвольными.
6.2. ЯЗЫКИ МП-АВТОМАТОВ 247 Таким образом, как только Рк приходит в допускающее состояние после прочтения ю, Рн опустошает свой магазин, также прочитав»е. Во избежание имитации случая, когда Рк случайно опустошает свой магазин без допуска, Рн должен также использовать маркер Х, на дне магазина. Маркер является его стартовым символом и аналогично конструкции теоремы 6.9 Р, должен начинать работу в новом состоянии р,, единственная функция которого — затолкнуть стартовый символ автомата Рк в магазин и перейти в начальное состояние Р„; В сжатом виде конструкция представлена на рис. 6.7, а ее формальное описание приводится в следующей теореме.
бой7 е. Нач Рис. 6.7. Ри ииитирует Ре и ооустои»ает свой мигал»»н тогда и только тогда, когда Ре достигает заключительного состоянии Теорема 6,11. Пусть Е = ЦР»») для некоторого МП-автомата Рк = ((», л., Г„б»ч йт Ув, с). Тогда сушествует такой МП-автомат Рм у которого 6 = д7(рн). Доказательство. Конструкция соответствует рис. 6.7. Пусть Рн = (О 0 (рв р), т, Г 0 Ра) бк, ре, Хл) где б» определена следующим образом. 1 бн(ре, а, Хв) = ((суе, УвХе)). Работа начинается с заталкивания стартового символа ав- томата Р»: в магазин и перехода в его начальное состояние. 2. Для всех состояний д из Д, входов а из г, или а= к и магазинных символов У нз Г бк(о, а, У) содержит все пары из б»(о, а, У), т.е. Рн имитирует Р»; 3.
Для всех допускаюших состояний а из Р и магазинных символов 1' из ГЦ (Хв) бн(д, я, У) содержит (р, а). По этому правилу, как только Р» допускает, Рн может начать опустошение магазина без чтения входных символов. 4. Для всех магазинных символов )'нз Г() (Хв), Бн(р, к, У) = ((р, а)). Попав в состояние р (только в случае, когда Р»: допускает), Рн выталкивает символы нз магазина до его опустошения. Входные символы при этом не читаются.
Теперь нужно доказать, что и 6 КРн) тогда и только тогда, когда и 6 ЦР»). Идеи аналогичны теореме 6.9. Достаточность представляет собой непосредственную имитацию, а необходимость требует проверки ограниченного числа действий, которые может совершить МП-автомат Рн. ГЛАВА 6. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 248 (Достаточность) Пусть Оз,, н, Хе) !- (су, е, а) для некоторого допускающего состояния л с н цепочки а в магазине.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
