Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
4) А-языки были независимо введены также Н. Хомским. — Прим. ред. 160
Часть II. Некоторые замечательные классы языков
10.1.1. Определение
Автоматная грамматика, или А-грамматика, имеет алфавит V = Va U Vt (Va — вспомогательный, Vt — основной), где VAf]VT = 0, Va = {Ai\ 1 причем Ai — аксиома, Vt = {aj|0-</-<m} и
правила вида
At-* O1Ak (правосторонние)
или
A1-* AkO1 (левосторонние)
(в каждой грамматике — только правосторонние или только левосторонние!), а также вида
At-*ah At-*E
(словарные или терминальные правила).
Стрелка в X-* Y (как и выше) означает «подставить Y вместо X».
Пример. V = {Р, Q} U [a, b}; аксиома — Р\
Р-*аР
(0Прав)
P-
Q-Q-
• aQ ¦bQ ¦b
Эта грамматика задает язык, состоящий из всевозможных цепочек, устроенных следующим образом: последовательность из а, а за ней — последовательность из Ь, т. е.
{ambn I m, п> 0).
Тот же самый язык может быть описан другой грамматикой
P-* Pb
(OMB) :
P-* Qb Q->Qa Q-* а
Приведем в качестве примера вывод цепочки asb2 в грамматике
(Оправ) •
Р-*аР~* ааР -* aaaQ -* aaabQ -* aaabb.
Замечание. Любой конечный язык является А-языком. Множество, содержащее п цепочек, — {/,, f2, ..., f„}, ft = ап ... aikl, — может быть описано следующей А-грамматикой:
G = [Р-*ацАп] An-*O12A12; ...; Aitkr2-*aitk.-iAltl
Ahkt-X-*-аЛі I 1 <i<n}. Гл. X. Автоматные языки и конечные автоматы
161
tO.1.2. Синтаксические структуры
Подобно КС-грамматике, А-грамматика задает некоторое множество древовидных структур.
Пример. Цепочке aaabb, выведенной в (GnpaB), отвечает структура
b
? скобочной форме эта структура имела бы следующий вид:
(a(a(a(b(b))))).
PPPQQ
Структуру вида
pP P
П--Г-
* * а
иногда называют «правоциклической».
Если бы для вывода цепочки мы воспользовались грамматикой (Gneв), то эта цепочка имела бы («левоциклическую») структуру
P
q /> '
или в скобочной записи
(((((а)а)а)Ь)Ь).
pppqq
10.1.3. А-языки и Комит
Известный язык программирования Комит1) может быть описан посредством А-грамматики. Комит включает команды (правила) следующего вида:
NOMl ESYMB = ESYMBVINST, .... NOM2,
левая часть правая часть
где
') См. статью В. И н г в е «Язык для программирования задач машинного перевода» в «Кибернетическом сборнике», в, 1963, ИЛ, M., стр. 229—266. — Прим. перев. 162
Часть II. Некоторые замечательные классы языков
а) NOMl—имя (номер) данной команды.
б) S SYMB позволяет искать в памяти машины определенные последовательности символов, имеющие в Комите статус единой последовательности.
в) S SYMB' выполняет над символами, обнаруженными левой частью команды, определенные операции.
Таким образом, SSYMB содержит операнды, a SSYMB' — операции. Формально S SYMB и S SYMB' суть последовательности любых слов, цифр или иных символов, разделенных знаком +. Например:
1 + МЯЧ + $ + СТАКАН + 2.
Команды Комита выполняются строго слева направо1).
г) INST обозначает некоторую последовательность команд, которая должна быть применена к результату работы правой части правила.
д) NOM2 — имя (номер) команды, которая должна выполняться непосредственно вслед за данной.
Число элементов, фигурирующих в S SYMB и в S SYMB', ограничивается только реальным объемом памяти используемой ЭВМ. Однако на соотношения между S SYMB и S SYMB' могут быть наложены определенные ограничения. Для того чтобы Комит был А-языком, операции в S SYMB' должны быть определены независимо от операндов. Допустим, однако, что мы хотим, чтобы в ходе трансляции программы, написанной на Комите, можно было проверять, отвечает ли каждой операции в S SYMB' определенный операнд в S SYMB; тогда нам придется ввести ограничения, связывающие левую и правую части команды. Если подобные ограничения разрешается неограниченно вставлять друг в друга, то Комит уже не будет А-языком.
§ 10.2. КОНЕЧНЫЕ АВТОМАТЫ
Напомним, что КС-грамматикам мы поставили в соответствие автоматы с магазинной памятью; аналогичным образом мы поставим в соответствие А-грамматикам машины весьма специального ьида — так называемые конечные автоматы.
10.2.1. Описание конечных автоматов
Конечный автомат может принимать конечное число состояний Si.....Sp. Он имеет читающую головку и ленту, которая перемещается под этой головкой. Лента разбита на ячейки; в каждой ячейке может находиться один символ из словаря V = [at | О •^iя}, где ао = В играет роль пустого символа.
') Именно этим обеспечивается «автоматность» языка. — Прим ред. Гл. X. Автоматные языки и конечные автоматы
163
Одно из состояний автомата — So — выделено и называется на¦ чальным состоянием.
В В в % ah aI aI В В
п
10.2.2. Функционирование конечного автомата
На содержательном уровне функционирование конечного автомата можно представить себе следующим образом. На ленте записывается цепочка а є V*; будем считать, что все ячейки слева и справа от а заполнены символами В. Автомат начинает работать в состоянии S0, причем головка обозревает самый левый символ цепочки а. Прочтя обозреваемый символ, автомат переходит в новое состояние и перемещает ленту на одну ячейку влево. Переход в новое состояние выполняется в соответствии с одной из команд, имеющих вид
