XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 99
Текст из файла (страница 99)
Если в системе команд 6 МП-автомата М есть команда (8'.8), то М может в данный момент времени выполнить зту команду, если и только если в данный момент времени его блок управления находится в состоянии о, головка обозревает входной символ а (при условии, что а ф Л), а верхним символом магазина является символ Я. Выполнение команды (8.8) состоит в замене верхнего символа магазина цепочкой у (как зто описано вьппе), переходе блока управления в состояние т (которое может и совпадать с состоянием д) и в продвижении головки на одну ячейку вправо (если а в команде (8.8) не есть пустая цепочка А) (рис. 8.32). Если же в команде (8.8) а = А, то такую команду МП- автомат может выполнить всякий рэз, когда его блок управления окажется в состоянии о, а верхним символом магазина будет символ Я.
В этом случае выполнение команды никак не 629 В.4. Магааннные автоматы Входная лента Входная лента Рнс. 8.32 зависит от содержимого входной ленты, а после ее выполнения головка остается на прежнем месте. Рассмотренную вьппе процедуру выполнения команды вида (8.8) называют шагом (или тпактпом) работпы МП-автпоматпа (ври а = Л такт работы называют Л-тпактпом). Предположим теперь, что в множестве состояний Я блока управления МП-автомата М с системой команд 6 фиксировано некоторое начальное состполние де и подмножество заключитпельных состполний Р. Пусть в какой-то начальный момент времени блок управле ния МП-автомата М находится в начальном состоянии де, на ленте записана непустэл цепочка х, головка обозревает первую ячейку ленты и, следовательно, первый символ цепочки х является обозреваемым, а в магазине записан только один специальный символ Яе, называемый начальным символом магазина.
Тогда, если МП-автомат М, выполняя некоторую последовательность команд иэ б, прочитывает полностью цепочку х, в результате чего блок управления переходит в некоторое заключительное состояние ду Е г', говорят, что МП-автомат М допускает (распознает, воспринимает) цепочку/х, которую называют допустпимой цепочкой МП-автпоматпа. Множа. ство всех допустимых цепочек МП-автомата М образует язык, допускаемый этим МП-автпоматпом.
63Р 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Далее мы докажем, что язык любого МП-автомата является КС-языком и, наоборот, любой КС-язык есть язык некоторого МП-автомата. В этом смысле мы и говорим об МП-автоматах как о „распознавателях" КС-языков: всякий МП-автомат допускает те и только те цепочки входных символов, которые порождаютсл некоторой КС-гряммашикой. Но чтобы доказывать какие-либо утверждения об МП-автоматах, нужно сначала дать строгое математическое определение этого понятия, не апеллируя уже к наглядным, но не определенным формально идеям ленты, магазина, головки и т.п. Формализация изложенного вьппе описания проводится во многом аналогично построению определения порождающей грамматики. Определение 8.7.
МП-автомат задается упорядоченной семеркой М = Я~ К Г Чо Р ~о, б), где Я вЂ” конечное множество состояний; У вЂ” алфавит, называемый входным алфавитом; à — алфавит, называемый магазинным алфавитом; де Е Я вЂ” начальное состояние; г' С Я— подмножество заключительных состояний; Яз е à — начальный магазинный символ; б — система команд, определенная как конечное множество команд, каждая иэ которых записывается в виде (8.8): яоЯ -~ г7, где знак „-~" (стрелка) — внешний символ (не принадлежащий ни одному из указанных алфавитов); д, г Е ф а Е У 0 (Ц; Я Е Г; 7 Е Г'. Замечание 8.8. Нелишне обратить внимание на то, что упоминание о ленте и магазине в приведенном вьппе формальном определении совершенно необязательно. Формально для определения МП-автомата достаточно задать два алфавита, конечное множество состояний, выделив в нем начальное состояние и подмножество заключительных состояний, а также 631 8.4.
Магааиииые аатаматы систему команд. Образы ленты, магазина, да и сам термин и состояние", являются метафорами, которые позволяют связать формальное определение с его содержательной интерпретацией, идеей некоего „устройства" для чтения слов, с описания которого мы начали этот параграф. Любую цепочку в алфавите т' будем называть входной цепочкой, а сами элементы входного алфавита — входными символами; точно так же любую цепочку в алфавите Г будем называть магазинной цепочкой, а символы этого алфавита— магазинными символами. Упорядоченную тройку до знака „~а (стрелки) в записи команды называют левой част»ью кома»ды, а упорядоченную пару после знака „->" — »равой часе»ью нома»ды.
Пример 8.14. Рассмотрим МП-автомат М1 =Яче,т,ь), (0,1), С2,0), Че, Ио), ~А) с таким множеством команд бд. ~,Ог- 6, Ог, д100~д1 00, 4?110 + 4?2лФ дг10 -+ дэ Л, ~,Лг- деЛ. На рис. 8.33 проиллюстрировано выполнение первых двух команд. При записи системы команд этого конкретного МПавтомата мы в правых частях первых двух команд отделили магазинную цепочку от состояния пробелом для того, чтобы не возник соблазн прочитать левую и правую части этих команд одинаково. Таким приемом записи мы хотим подчеркнуть, что левая часть команды МП-автомата — упорядоченнай тройка, а правая — упорядоченная пара.
8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Входная лента Входная леита ии ия Входная леита азин Рис. 8.33 Замечание 8.9. Систему команд МП-автомата можно понимать как способ определения некоторой конечной функции, которую называют функцией переходов МП-аепюматпа (по аналогии с функцией переходов конечного автоматла).
Эта функция может быть определена как отображение вида о: Я х (У о (Л)) х Г -+ Вш(ц х Г ), где использовано обозначение я 1п(А) для множества всех конечных подмножеств множества А. „Динамику" МП-автомата, т.е. процесс перехода его из одного состояния в другое в соответствии с обоэреваемыми символами на ленте и содержимым магазина, удобнее всего описывать в терминах конфигураций.
Для этого общее понятие конфигурации автомата, которое на интуитивном уровне 633 оА. аеагатаяаые автоматы было введено в Т.б, необходимо уточнить применительно к МП-автомату и определить также отношение выводимости на множестве конфигураций. Определение 8.8. Конфигурациеб МП-автомата М называют упорядоченную тройку вида (д, х, ~8), где д е Я— состояние, х Е 'т" ' — входная цепочка, ~3 — магазинная цепочка.
Конфигурацию С' = (т, ш, уа) называют непосредственно выводимой из конфигурации С = (д, ато, Яа), если в множестве команд МП-автомата есть команда (8.8). Отношение непосредственной выводимости на множестве конфигураций МП-автомата М обозначаем ~м, используя запись С~-щС' (и опуская, если это не вредит пониманию, обозначение самого МП-автомата). Итак, непосредственная выводимость (ч, аш, Яа) ~м(т, ю, уа) (8.9) имеет место тогда и только тогда, когда в системе б команд МП-автомата М есть команда (8.8), которую в этом случае называют применимой к конфигурации (д, аю, Яа). Таким образом, неформально конфигурация показывает состояние блока управления, непрочитанную часть входной цепочки (первый символ этой цепочки, если она не пуста, является обозреваемым) и содержимое магазина (первый символ магазинной цепочки р", если она не пуста, есть верхний символ магазина).
Если вторая компонента конфигурации — пустая цепочка, то это означает, что входная цепочка прочитана полностью. Если же пуста третья компонента, то это означает, что пуст магазин. На рис. 8.33 изображены (в терминах приведенного вьппе содержательного описания) две конфигурации МП-автомата из примера 8.14, причем вторая конфигурация непосредственно выводится вз первой. Понятие непосредственной выводимости, таким образом, формализует данное вьппе понятие такта '(или 634 В. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ шага) работы МП-автомата.
Заметим, что если в (8.9) и в команде (8.8) а = Л, т.е. имеет место Л-такт, то команда (8.8) применима к любой конфигурации, у которой (говоря неформально) состояние блока управления есть д, а верхний символ магазина — Я, причем, подчеркнем это, независимо от содержимого входной ленты (т.е. для любой входной цепочки ю). Если же а есть входной символ, то применимость команды к конфигурации определяется состоянием, обозреваемым символом на ленте и верхним символом магазина. Любую конфигурацию вида (дс, х, Яс) называют начальной, а любУю конфигУРацию вида (9у, Л, Л), где ду Е Р,— заилючитаельиой. Обратим внимание на то, что заключительная конфигурация — это конфигурация с пустым магазином.
Множество всех заключительных конфигураций находится, таким образом, во взаимно однозначном соответствии с множеством заключительных состояний МП-автомата. Из заключительной конфигурации не может быть выведена ни одна конфигурация, так как к ней не применима ни одна команда. Конфигурацию МП-автомата, не являющуюся заключительной и к которой не применима ни одна команда, называют тттуацковой. Определение 8.9. Выводом ма множестпве ион9тцгураций МП-автаоматпа М называют последовательность Се, С1, ..., С„, ...
(конечную или бесконечную) таких его конфигураций, что для любого 1 > О имеет место С, 1- С;+и если С;+1 существует. Если вывод конечен и ф— его последняя конфигурация, то число и называют длиной вывода. В этом случае будем говорить, что вывод Сз, Сы ..., С„связывает конфигурацию Сс с конфигурацией С„. Конфигурацию С' называют выводимой из конфигурации С, обозначая это как С ~-' С', если существует вывод, связывающий С с С', т.е. вывод Сз, См ..., С„, такой, что Сс = С, ф С„= С'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
