Главная Промышленная автоматика.

входной цепочки, а К* - цепочка в магазине (будем считать что верхний символ распололен слева), $ - правый концевой маркер (SSUK).

Суидествует два типа операций, обозначаемых и W, и соответственно два типа команд. Команда первого типа в случае XkK применима к конфигурации [к, aw, а); в результате она дает конфигурацию (к, w$y уа), т. е. к содержимому магазина приписывается у (или ничего, если у = е) и, если сдвигается входная головка. В случае X = \i она применима к конфигурации (к, aw$, ка), если у = е, и [к, aw$, а), если у--к"у. Для первой конфигурации она дает (к, w$, а), т. е. из магазина извлекается очередное состояние. Для второй конфигурации она дает {к\ w, уос), т. е. очередным состоянием становится первый символ цепочки у, а остальная ее часть помещается в магазин.

Команда второго типа имеет вид

ka->k

где /-К и ftK. Она применима к конфигурации [к, aw<,, т) и дает {к\ w%, а), т. е. она применима, если г - верхний символ магазина, п в этом случае она удаляет его из магазина. Заметим, что применимость команды второго типа зависит от содержимого магазина, а первого типа - нет.

Символ, стоящий слева от знака образует левую часть команды. Команду с левой частью k назовем -командой. Последовательность fe-команд

«1 - Х, ка ~J-X, ..., ка„ -> „ будем называть к-комплектом, если из С 2 и г</ следует,

что (7,£2. Будем записывать его в виде ка--Х]...]

а,, -> Заметим, что команды -комплекта упорядочены так, чтобы команды с аХ предшествовали командам с а, -е.

Определение. СМЦ-распознавателем назовем пятерку М = .-(К, 2, R, /), где К -алфавит состояний (оп же магазинный алфавит), S - входной, или терминальный, алфавит, не пересекающийся с К, R - конечное множество й-комплектов (пе более одного для каждого й), kfK - начальное состояние, /К - заключительное состояние.

Если первая из команд й-комплекта распознавателя М, применимая к конфигурации {к, w$, у), дает {к, w$, у), будем писать (й, y)h-Ai(, w, у).

Языком, определяемым распознавателем УИ, назовем множество

L (М) {wZl [к,, w$, /) \-h if, $, е)}

Пример 3. Рассмотрим CMR-распознаватель М = {{ко, к, /}, {а, Ь]у R, К /) котором R состоит из комплектов

-а->к\е->11

кЬ > р, I е -> II

Для входной цепочки ааЬ$ распознаватель М сделает такую последовательность тактов:

(k,,aab$, /)Ь-(о. kj) Н(о. Ь$, k,kj) Ь(1. Ь$, kj) b(feu $, f) Ь (/. 5, е) п

Определение. CMR-распознаватель назовем слабым, если все его команды первого типа.

Для слабого CMR-распознаватсля М={К, 2, R, ftp, /) определим соответствующую КС-грамматику G-{N, 2, Р, 5), положив N К, 5 = 0 и для каждой команды из R вида ка -к

включив в Р правило к-ак у, а для команды вида ка->-р.-

правило к-ау.

Пример 4. Распознаватель М из примера 3 слабый и ему соответствует КС-грамматика

-+ akji- 1 е к-Ь\е

Она получается из грамматики примера 2 очевидным переименованием нетерминалов. П

Легко видеть, что если wL(M), то каждый шаг слабого CMR-распознавателя М соответствует шагу левого вывода цепочки W в грамматике Gy, на котором применяется соответствующее правило. Следовательно, L(M)L(G). Но не обязательно L(M)=L(G).

Слабый CMR-распознаватель М назовем адекватным, если

i(M) = L(Gд,).

Упр. 10. Покажите, что если в каждом fe-комплекте слабого CMR-распознавателя М отбросить для каждого aSuf} все

гравила вида ка X, кроме первого, то получится распознаватель М, эквивалентный М.

Упр. 1, Покажите, что если у слабого CMR-распознава-

теля М команды вида ке и то

>Х удовлетворяют условиям у=е



А-Ху... \Х.у... Х„ I... I Xft,... X

назовем помеченный ориептировапный граф, изображенный на рис. Д.1. В этой диаграмме вершина I начальная, вершина / заключительная, а в нумерации вершин важно лишь то, что она взаимно однозначна. Нетерминал Л считается именем диаграммы d.



рис. Д.1. КС-диаграмма.

КС-диаграммером, соответствующим КС-грамматике G = (N, S, Я, S), назовем четверку Мо = (2, N, £>, d), где D = и d-начальная диаграмма.

Пример 5. КС-диаграммер Мс, =({о, Ь}, {S, Л}, D, dg), соответствующий КС-грамматике G примера 2, состоит из двух КС-диаграмм, изображенных на рис. Д.2. □

S: ( 1


Рис. д.2. КС-диаграммер.

В общем случае синтаксической диаграммой (С-диаграммой) над парой непересекающихся алфавитов 2 и Д назовем конечный помеченный ориентированный граф, вершины которого занумерованы и выделены одна начальная вершина (с номером 1) и одна или несколько заключительных вершин. Каждая дуга помечена символами либо oSujt}, либо d/, либо (ii, О ("Содержательно, i-номер заключительной вершины диаграммы, обозначенной d и имеющей несколько заключительных верншн). В начальную вершину дуги не входят, из заключительной - не выходят.

Диаграммером назовем четверку М = (2, Д, D, d), где Е - конечный входной алфавит, Д -конечный диаграммный алфавит (его символы служат именами или обозначениями диаграмм), конечное множество С-диаграмм над алфавитами 2 и А (причем 2пД0 и между Д и D установлено взаимно однозначное соответствие, именующее диаграммы), (i,,- начальная диаграмма с одной заключительной вершн1юй.

Состоянием диаграммера М назовем пару (d, /), где dD п г -номер некоторой вершины диаграммы d, т. е. состояние- это по существу вершина диаграммы, обозначаемая как пара. Множество состояний Q является также магазинным алфавитом диаграммера М (как и у CMR-распозиавателя). Конфигурация Диаграммера имеет вид {[d, i), w>,, y), где [d, 0€Q~тeкyщee состояние, ш £ 2* - необработанная часть входной цепочки, Y€Q*-магазинная цепочка (верхний символ слева), $ -концевой маркер входа и магазина (Si2uQ).

Определим один такт работы диаграммера М, т. е. отношение на его конфигурациях. Пусть дана конфигурация [id, i), $. TS). где ai либо aw = e.

(а) соответствующая КС-грамматика псевдоразделенная,

(б) М эквивалентен простому МП-распознавателю М = Ма, соответствующему грамматике Gij, и, значит, М адекватен тогда и только тогда, когда Gji - слаборазделенная грамматика. Указание. Покажите, что (fe, w, ?)!-м(. у) тогда и только тогда, когда {w$, ky)\-M{w, ky).

Упр. 12. Для произвольного слабого CMR-распозиавателя М построите эквивалентный ему слабый CMR-распознаватель М, команды которого удовлетворяют условиям упр. П.

Упр, 13. Покажите, что для произвольного CMR-распозна-вателя можно построить эквивалентный ему ДМП-автомат, н обратно (т. е. CMR-распознаватели определяют в точности класс детерминированных КС-языков).

Рассмотрим теперь так называемый диаграммер Конвэя [1963]- МП-распознаватель, управляющее устройство которого задается конечным множеством D „синтаксических диаграмм". Содержательно, диаграмма d£D определяет некоторый „синтаксический тип", т. е. множество цепочек L, распознаваемых диаграммером при „прохождении" диаграммы d. Связь между d и в диаграм-мере аналогична связи между нетерминалом А и множеством цепочек, выводимых из Л, в КС-грамматике. Чтобы подчеркнуть эту связь, определим вначале синтаксические диаграммы частного вида, непосредственно связанные с КС-правилами.

Определение. КС-диаграммой d, соответствующей множеству Л-правил



(а) Если из вершины [d, i) выходит дуга, помеченная символом и входящая в вершину {d, j), то

{{d, /), aw$, у$)1-((, /)> V$)

т. е. делается переход из {d, i) в {d, j) по дуге, помеченной а, и сдвигается входная головка.

(б) Если условие в (а) не выполнено, но из [d, i) выходит дуга, помеченная именем диаграммы d или парой [d, /), то

т. е. состоянием становится начальная вершина диаграммы d\ а в магазине запоминается вершина [d, i), к которой надо вернуться позднее, когда будет пройдена диаграмма d.

(в) Если не выполнены условия ни в (а), ни в (б), но из (d, i) выходит дуга, помеченная е и ведущая в (d, j), то

{{d, i), aw$, y$)\-{{d, j), aw$, y$)

T. e. „пустая" дуга проходится в последнюю очередь без изменения входа и магазина.

(г) Если {d, i) - заключительная вершина, у (ii у) Yи дуга с меткой (d, i) ведет из (d, j) в (d, k), то

{(d, i), aw$, (d\ j)y%) + {{d, k), aw%, y$)

T. e. информация о следующем состоянии извлекается из магазина (как у CMR-раснознавателя). В этом случае диаграмма d уже пройдена, н надо перейти в (d, k) по дуге, соответствующей заключительной вершине [d, i).

Заметим, что для текущего входного символа а и текущей вершины [d, i) выбор выходящей из нее дуги играет роль выполнения очередной команды распознавателя. Пункты (а)-(в) показывают, что диаграммер, так же как простой МП-распознаватель и CMR-распознаватель, пытается сначала выполнить команду, помеченную символом й, и в последнюю очередь-команду, помеченную е. Отметим еще, что диаграммер является, вообще говоря, недетерминированным распознавателем, так как может случиться, что из (d, i) можно выйти по разным дугам, т. е. выполнить разные команды.

Пусть (d, i) - заключительная вершина диаграммы d. Языком, распознаваемым диаграммером м при прохождении диаграммы а из ее начальной вершины в вершину (d, i), назовем множество

L(,.o-={€2*((rf, 1), w%, %)V-4(d, i), $, $)}

Если d имеет одну заключительную вершину i, то вместо/.(d. о будем писать L. Язык, распознаваемый диаграммером М, - это множество L(m)=La.

Упр. 14. Покажите, что

(а) если m(j = {x, N, D, d) - КС-диаграммер, соответствующий КС-грамматике G-:(N, 2, Р, 5), то 1 = {w\A=±>bw} и, в частности, l{mg) l{g).

(б) если g - псевдоразделенная грамматика и ма - соответствующий ей простой МП-распознаватель, то l{m(j)=l{mg) (и, значит, если грамматика g слаборазделснная, то l{mq)-= r--l{g)).

Упр. 15. Для произвольной КС-грамматики постройте эквивалентный ей КС-диаграммер.

Упр. 16. Для произвольного диаграымера постройте эквивалентный ему (недетерминированный) МП-автомат.

Из упр. 15 и 16 следует, что диаграммеры распознают в точности класс КС-языков.

Наложим на диаграммер ограничение, аналогичное LL (1)-условию или условию разделеппостп для КС-грамматики и позволяющее сделать детерминированным выбор дуги на каждом шаге.

С каждой меткой X, помечающей дугу диаграммера М, свяжем соответствующее ей „множество первых символов" F{X), определяемое так:

(1) F{a) = \a\ для йбиИ.

(2) если d обозначает диаграмму с одной заключительной вершиной, то

F{d) = {a\{ae и awLa) или (ае и eL))

(3) F((rf, i)){a\{a и а1юц,1)) или {а = е w еЦл i))).

Назовем диаграммер м разделенным, если для каждой вершины [d, i), из которой выходят п дуг, помеченных метками 1, Х„, множества F{X), F{XJ попарно не пересе-

каются. Для разделенного диаграммера м доопределим отношение -: для текущего символа а и вершины (состояния) (d, i) выбирается выходящая из нее дуга с меткой X, для которой «6F(X), а если таковой нет, то дуга, для которой eF(X). Заметим, что выбрать можно только одну дугу.

Упр. \1, Покажите, что если КС-диаграммер mq, соответствующий КС-грамматике G, разделенный, то g эквивалентна псевдоразделенной грамматике g и l[mq) = l(mg) для соответствующего g простого МП-распознавателя мс (ср. с упр. 14(6)).

В работе [Ломет, 1973] изучаются детерминированные диа-граммеры следующего специального вида.

Определение. Диаграммер М = (2, Д, D, d) назовем Ь-диа-раммером, если в каждой его диаграмме все дуги, выходящие

- Ахо, Дж. Ульман, т. i 417





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 [68] 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.002