Магазинные автоматы, страница 2

Магааиииые аатаматы систему команд. Образы ленты, магазина, да и сам термин и состояние", являются метафорами, которые позволяют связать формальное определение с его содержательной интерпретацией, идеей некоего „устройства" для чтения слов, с описания которого мы начали этот параграф. Любую цепочку в алфавите т' будем называть входной цепочкой, а сами элементы входного алфавита — входными символами; точно так же любую цепочку в алфавите Г будем называть магазинной цепочкой, а символы этого алфавита— магазинными символами.

Упорядоченную тройку до знака „~а (стрелки) в записи команды называют левой част»ью кома»ды, а упорядоченную пару после знака „->" — »равой часе»ью нома»ды. Пример 8.14. Рассмотрим МП-автомат М1 =Яче,т,ь), (0,1), С2,0), Че, Ио), ~А) с таким множеством команд бд. ~,Ог- 6, Ог, д100~д1 00, 4?110 + 4?2лФ дг10 -+ дэ Л, ~,Лг- деЛ. На рис. 8.33 проиллюстрировано выполнение первых двух команд. При записи системы команд этого конкретного МПавтомата мы в правых частях первых двух команд отделили магазинную цепочку от состояния пробелом для того, чтобы не возник соблазн прочитать левую и правую части этих команд одинаково.

Таким приемом записи мы хотим подчеркнуть, что левая часть команды МП-автомата — упорядоченнай тройка, а правая — упорядоченная пара. 632 О. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Входная лента Входная лента нн Входная лента азин Рис. 3.33 Замечание 8.9. Систему команд МП-автомата можно понимать как способ определения некоторой конечной функции, которую называют функцией переходов МП-аетоматпа (по аналогии с функцией переходов конечноео автоматпа). Эта функция может быть определена как отображение вида д: Ч х (У0(Ч) х Г-+гш(Ях Г'), где использовано обозначение яш(А) для множества всех конечных подмножеств множества А. ф „Динамику" МП-автомата, т.е.

процесс перехода его из одного состояния в другое в соответствии с обозреваемыми символами на ленте и содержимым магазина, удобнее всего описывать в терминах конфигураций. Для этого общее понятие конфигурации автомата, которое на интуитивном уровне 633 8А. аеагатаяаые автоматы было введено в Т.б, необходимо уточнить применительно к МП-автомату и определить также отношение выводимости на множестве конфигураций. Определение 8.8. Конфигурациеб МП-автомата М называют упорядоченную тройку вида (д, х, ~8), где д е Я— состояние, х Е 'т" ' — входная цепочка, ~3 — магазинная цепочка.

Конфигурацию С' = (т, ш, уа) называют непосредственно выводимой из конфигурации С = (д, ато, Яа), если в множестве команд МП-автомата есть команда (8.8). Отношение непосредственной выводимости на множестве конфигураций МП-автомата М обозначаем ~м, используя запись С~-щС' (и опуская, если это не вредит пониманию, обозначение самого МП-автомата). Итак, непосредственная выводимость (ч, аш, Яа) ~м(т, ю, уа) (8.9) имеет место тогда и только тогда, когда в системе б команд МП-автомата М есть команда (8.8), которую в этом случае называют применимой к конфивурации (д, аю, Яа).

Таким образом, неформально конфигурация показывает состояние блока управления, непрочитанную часть входной цепочки (первый символ этой цепочки, если она не пуста, является обозреваемым) и содержимое магазина (первый символ магазинной цепочки р", если она не пуста, есть верхний символ магазина). Если вторая компонента конфигурации — пустая цепочка, то это означает, что входная цепочка прочитана полностью.

Если же пуста третья компонента, то это означает, что пуст магазин. На рис. 8.33 изображены (в терминах приведенного вьппе содержательного описания) две конфигурации МП-автомата из примера 8.14, причем вторая конфигурация непосредственно выводится вз первой. Понятие непосредственной выводимости, таким образом, формализует данное вьппе понятие такта '(или 634 В. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ шага) работы МП-автомата. Заметим, что если в (8.9) и в команде (8.8) а = Л, т.е. имеет место Л-такт, то команда (8.8) применима к любой конфигурации, у которой (говоря неформально) состояние блока управления есть д, а верхний символ магазина — Я, причем, подчеркнем это, независимо от содержимого входной ленты (т.е.

для любой входной цепочки и~). Если же а есть входной символ, то применимость команды к конфигурации определяется состоянием, обозреваемым символом на ленте и верхним символом магазина. Любую конфигурацию вида (дс, х, Яс) называют начальной, а любУю конфигУРацию вида (9у, Л, Л), где ду Е Р,— заттлючитаельиой.

Обратим внимание на то, что заключительная конфигурация — это конфигурация с пустым магазином. Множество всех заключительных конфигураций находится, таким образом, во взаимно однозначном соответствии с множеством заключительных состояний МП-автомата. Из заключительной конфигурации не может быть выведена ни одна конфигурация, так как к ней не применима ни одна команда. Конфигурацию МП-автомата, не являющуюся заключительной и к которой не применима ни одна команда, называют тттуаиковой. Определение 8.9.

Выводом иа множестпве иоивтигураций МП-автаоматпа М называют последовательность Се, С1, ..., С„, ... (конечную или бесконечную) таких его конфигураций, что для любого 1 > О имеет место С, 1- С;+м если С;+1 существует. Если вывод конечен и ф— его последняя конфигурация, то число и называют длиной вывода. В этом случае будем говорить, что вывод Сз, Сы ..., С„связывает конфигурацию Сс с конфигурацией С„. Конфигурацию С' называют выводимой из конфигурации С, обозначая это как С ~-' С', если существует вывод, связывающий С с С', т.е. вывод Сз, См ..., С„, такой, что Сс = С, ф С„= С'.

в.4. Магааинвые автоматы В частности, при и = 0 получаем, что любая конфигурация выводится сама иэ себя; при и = 1 получаем непосредственную выводимость С' из С. В общем случае говорят, что конфигурация С' выводится из конфигурации С за и шагов, записывая при этом С 1-" С'. Желал подчеркнуть, что существует вывод ненулевой длины конфигурации С' из конфвгурации С, т.е. С 1-" С' и и > О, записывают С 1-+ С'.

Таким образом, понятие выводимости для конфигураций МП-автомата вводится аналогично таковому для грамматики. И к тому же сохраняется полная аналогия с понятием дос~иижимости в ориентиврованнмх гра4ах. В терминах конфигураций может быть дано и строгое определение языка МП-автомата. Определение 8.10. Входную цепочку х называют допустимой цепочкой МП-автомата М (см. определение 8.7), если на множестве конфигураций М существует вывод, связывающий начальную конфигурацию (дг,х,ле) с заключительной конфигурацией (ду, Л, Л), где еу Е Р, т.е. Язык, допускаемый МП-автоматом М (или просто язык МП- автомата М), — это множество всех его допустимых цепочек. МП-автоматы М~ и Мэ называют экенеалентиныкн, если их языки совпадают, т.е.

ЦМ~) = ЦМэ). Любой вывод на множестве конфигураций МП-автомата, связывающий начальную конфигурацию Се — — (де,х,Яе) с одной из заключительных, называют допускающей иоследоеатиелъностиью конфигураций длл цепочки х. Цепочка х принадлежит языку ЦМ) тогда и только тойда„когда для нее существует допускающая последовательность конфигураций. Тем не менее может оказаться так, что даже в том случае, когда х е Ь(М), из начальной конфигурации Се можно вывести отнюдь не только заключительную конфигурацию. 838 8.

КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Мо = ((до,д1,дг), (а,6), (Я, а,ь), 9о,(дз), Я, Ьз) Можно доказать, что этот МП-автомат допускает зеркальный язык 1хх~ Е (а, Ь) ), где х обозначает инверсию ивиочии х. Приведем допускающую последовательность конфигураций для цепочки аььа: (до аььа ~) ~ (ц (9о ЬЬа а~) Г (о) (9о Ь~~ Ьа~) ~ (о1 ~<,> (9„а, аг) 1-<„(д„Л, г) 1-Оц (9„Л, Л) (справа внизу под значками непосредственной выводимости подписаны номера применяемых команд). К начальной конфигурации (до, а66а, Я) применима только команда (1). После выполнения этой команды первый символ входной цепочки будет прочитан, а в магазине вместо одного символа Я окажется цепочка аЯ, т.е. символ а станет верхним символом магазина.

К полученной конфигурации (до, Ььа, аЯ) применима только команда (б), в результате выполнения которой будет прочитан еще один символ входной цепочки, т.е. ее второй символ 6, и в магазине окажется цепочка ЬаЕ. Пример 8.15. Пусть МП-автомат опРеДелен множеством команД бьс1 дову -+ доаЕ, 9оЫ -+ 9оЫ, 9оаа -+ 9оаа, чоаа -+ 91Л, 9оаь -+ доаь, 906а — > ЧОЬа, доЬЬ -+ 9оЬЬ, доьь-+ д1Л 91аа -+ 91Л, 9166- 91Л, 91ЛЯ- 9,Л. (1) (2) (3) (4) (5) (б) (7) (8) (9) (10) (11) 637 8.4. Магаэявяые автоматм К третьей конфигурации записанного вьппе вывода применимы две команды: (7) и (8).

Выбирая команду (8), мы тем самым читаем третий символ входной цепочки, а верхний символ магазина, совпавший с указанным символом входной цепочки, „выталкиваем" иэ магазина, после чего верхним символом магазина окажется уже символ а, т.е. возникнет конфигурация (9м а, аЯ). Заметим также, что после выполнения команды (8) МП-автомат Мг окажется в новом состоянии дь Применив к конфигурации (9м а, аЯ) единственную применимую к ней команду (9), получим конфигурацию (д~, Л, 2), т.е. входная цепочка прочитана полностью, а в магазине остался символ Я. Применяя опять-таки единственно возможную для такой конфигурацию команду (11), мы убираем символ Я иэ магазина, тем самым опустошая его, и переходим в заключительное состонние 9э. В то же время, если бы после третьей конфигурации было выбрано „неудачное продолжение", т.е.