Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 61
Текст из файла (страница 61)
мо множество операций определяется множеством правил грамматики, а нх последовательность — структурой конкретного дерева вывода. Опишем этот процесс более формально на примере дерева вывода для выражения а Ь+а ° с (рис. 7.7). На этом рисунке нетерминальные вершины выделены кружками и обозначены аь..,, аь Кроме того, каждая вершина помечена соответствующим ей правилом р~ грамматики) индекс 1 — это номер правила а порядке его упоминания в примере 7тй Каждому, правилу р~ постаанм в соответствие функцию йч, число аргументов которой равно числу нетерминальных символов в правой части. Для правил, использованных в дереве рис, 7.7, этн функции таковы: рт:1 -г 1 + Т~ кг (хы хз) = хт+ хз', рз'.1 -~ Т М; аз (хт, хз) = хг хз; Рз: Т Т М; а, (хг, х,) = х, ° зб р„:Т а; й, =а, кроме того, йд=Ь.
2~э=с. Следует иметь в виду, что знаки + и в р~ и д~ имеют различное содержание, В синтаксических правилах р~ — это абстрактные символы, в функциях д~ — это осмысленные знаки знакомых нам арифметических операций, связанные с определеннымн действиямн над числами х, и хз. Пусть вершине пт соответствует правило рь В нашем примере аг имеет ие более двух потомков; обозначим через оз, левого потомка, 293 а через птз — правого потомка оь Поставим в соответствие вершине эт функцию-признак Ь(и,), определяеиый следующим образом: Ь(о,) =дь если рг — терминалыюс правило (1=12, 17, 18), Ь(э,) =Ф(Ь(эм), Ь(эм)), если рг — нетерминальное правило.
Нетрудно убедиться, что формально определенный таким образом вычислительный процесс для нашего примера осуществляет вычисление элементарных арифметических операций, соответствующих вершинам„ н передачу результатов от листьев к корню, т. е. работает так, как описано выше. Однако для выражений, содержащих деление, одной функции на правило недостаточно, Дело в том, что дсление на О недопустимо; поэтому, помимо арифметических операций, необходимо проверять, не равен ли делитель нулю, и если да, то передавать наверх, к корню, сообщение о бессмысленности всего выражения в целом. Это можно сделать, поставив в соответствие правилу рь кроме арифметической функции яь еще н преднкат корректности Рь который проверяет, определены ли вычисления для потомков вершины из (если рг — правило с делением, то Рь кроме того, проверяет, отличен ли от нуля результат вычисления в зм), и в случае положительного ответа разрешает вычисление в эз.'В этом случае каждой вершине эз с правилом р~ ставится в соответствие вектор признаков Ь(от) (Ьь ЬВ, где Ь, — признак корректности, а Ь, — результат вычисления арифметического выражения, для которого пз является корнем его дерева вывода (этот результат не определен, если 6~ ложен), Значением всего выражения является результат вычисления в корне дерева, Точную формализацию описанного процесса предоставляем читателю.
В общем случае размерность вектора признаков в вершние может быть любой; кроме того, сами признаки могут вычисляться как снизу вверх (в этом случае они называются синтезнруемыми), так и сверху вниз (в этом случае онн называются наследуемыми), Очевидно, что соответствующая грамматика однозначна. Различные варианты формализации вычисления семантики цепочек языка с помощью системы признаков в вершинах дерева, называемые атрибутнымн грамматиками (или атрибутнымн переводами, если значением цепочки языка является цевочка другого языка), изложены в [32, 51), Методы интерпретации текстов, основанные на синтаксически управляемых вычислениях, т.е.
на вычислениях, управляемых деревьями вывода, оказались весьма аффективными как в конкретных приложениях при разработке компиляторов для языков программирования, так н для понимания существа проблемы перевода в искусственных и естествекных языках. По-видимому, именно этим обстоятельством (наряду с удобством метаязыка Вакуса н возможностями его расширения на основе операций над КС-языкамн, описанных выше) объясняется широко распространенная тенденция представлять язык как КС-язык, даже если он н не вполне точно описывается КС-грамматикой.
Языки программи- 294 рования, наи правило, содержат ионструнцин, поторые не могут быть точно формализованы в терминах КС-правил. В этих случаях КС-правила сопровождаются различными ограничениями, соблюдение которых является дополнительным условием принадлежности цепочин языку. Использование деревьев вывода для интерпретации текстов объясняет также тот факт, что проблеыа синтаксического анализа — одна нз важвейгпнх в прикладной лингвистике — заключается не просто в распознавании принадлежности текста языку, а в построении синтаиснчесной струнтуры текста, соответствующей данной грамматние, что для КС-языиов равносильно построеннго дерева вывода.
ГЛАВА ВОСЬМАЯ АВтоййАТЫ ВД. ОСНОВНЫЕ ПОНЯТИЯ Определения. Конечным автоматом (в дальнейшем— просто автоматом) называется система 5=(А, ь1, 1', 6, Ц, в которой А=(аы ..., а„), Я =(дг, ..., гу ), $'=(ог, ..., оз)— конечные множества (алфавиты), а 6: ь)ХА-эьс и Л: сс'Х ХАэ-(' — функции, определенные на этих множествах. А называется входным алфавитом, Р— выходным алфавитом, Я вЂ” алфавитом состояний, 6 — функцией переходов, Л вЂ” функцией выходов.
Если, кроме того, в автомате 5 выделено одно состояние, называемое начальным (обычно будет считаться, что это д,), то полученный автомат называется инициалоным н обозначается (5, гу); таким образом, по неинициальному автомату с и состояниями можно а различными способами определить нницнальный автомат. Поскольку функции 6 н Л определены на конечных множествах, их можно задавать таблицами.
Обычно две таблицы сводятся в одну таблицу 6ХЛ: ЯХА-+ь)Х )г, называемую таблицей переходов автомата, или просто автоматной таблицей. Пример 8А. Таблица 8.! задает функции переходов и выходов для автомата с алфавитами А (аь аз, аз), б)=(дь гг2 ~ гг 3, гг' я) ) = (им и 2). Еще один распространенный и наглядный способ задания автомата — ориентированный мультнграф, называемый графом переходов нли диаграммой переходов. Вершины графа соответствуютсостояниям; если 6(дь аг) =гуе и Л(гуг, аг) =оь то из д, в д» ведет ребро, на котором написаны аг и оь Граф 295 переходов для табл. 8,! изображен на рис.
8.1. Кратные ребра пе обязательны; например, два ребра из д~ в д, можно заменить одним, на котором будут написаны обе пары аз(о~ и аг~оь Для любого графа переходов в каждой вергавлици дг шине д; выполнены следующие условия, которые называ- ются условиями корректности: 1) для любой входной буквы а~ имеется ребро, выходящее из дь на котором написано а~ (условие полноты); 21 любая буква а; встречается только на одном ребре, выходящем из д, (условие непротиворечи- чд, и~ Чо а, Чв Ч4 ~~! Ча Чз 94 Это традиционное определение «с многоточиями»; намного точнее и лучше читается индуктивное определение, к которому читатель, надеемся, уже привык: вости или детерминированности).
Для данного автомата Я его функции бз и Хз могут быть определены не только на множестве А всех входных букв, но и на множестве Аа всех входных слов. Для любого входного слова а=а;,а~ ...ад„'1 б(до а,,а,, ... ат ) =- б(б(... б(по а;,), ат,), ..., а;,),а~ь). а) б(дп а,) задается автоматной таблицей 5; б) для любого слова я~А' и любой буквы ау б (ао яат) = б (б (ао а), а ) . (8,1) С помощью расширенной функции б определяется (также индуктивно) расширенная функция Л: Л(оо яат) =Л(б(оо я), аз).
(8.2) Зафиксируем в автомате 5 начальное состояние и каждому входному слову я=апа~, а; поставим в соответствие слово ы в выходном алфавите: в =Л(9м аи)Л(дм а, а~,) ... Л(д„ап ... ат,). (8.3а) Это соответствие, отображающее входные слова в выходные слова, называется автоматным отображением, а также автоматным (или ограниченно детерминированнььи) оператором, реализуемым автоматом (5, е,), Иногда будем говорить кратко — оператор (5, д~) или оператор 5 (если автомат 5 — инициальный).
Если результатом применения оператора к слову я является выходное слово м, то это будем обозначать соответственно 5(аь я) =ь или 5(я) =в. Число букв в слове я, как обычно, называется длиной я и обозначается (а~ или 1(а). Автоматное отображение также удобно определить индуктивно: 5(рь а,) = Л(ао ат); 5 (до яа~) = 5 (до я) Л (б (ао я), а~)./ Автоматное отображение обладает двумя свойствами, которые следуют непосредственно из (8.3а), (8,3 б): 1) слова а и в=5 (а) имеют одинаковую длину: ) я) = )ы( (свойство сохранения длины); 2) если я=я~я» и 5(я~я») =вием где ) я~ ) = ~ ач ~, то 5(я~) =аб иначе говоря, образ отрезка длины 1 равен отрезку образа той же длины. Свойство 2 отражает тот факт, что автоматные операторы — это операторы без предвосхищения [17), т.
е. операторы, которые, перерабатывая слово слева направо, «не заглядывают вперед»: 1-я буква выходного слова зависит только от первых 1 букв выходного слова. Пример оператора с предвосхищепием— оператор, который слову я=ач...а; ставит в соответствие его отражение, т. е. слово а, .,.а;,; первая буква выходного слова равна здесь последней букве входного слова. Указанные два свойства были бы достаточными условиями автоматности отображения, если бы речь шла о беско- 297 печных автоматах, т.
е. автоматах с бесконечным Я. Для конечной автоматности этих условий недостаточно: в дальнейшем будут описаны отображения, которые удовлетворяют условиям 1 и 2, но не реализуются в конечном автомате, Введенные определения (8.1) — (8.3) наглядно интерпретируются на графе переходов. Если зафиксирована вершина дь то всякое слово а=а;,...а; однозначно определяет путь длины Ф из этой вершины [обозначим его (дь а)), на й ребрах которого написаны соответственно буквы азн..„а~з, Поэтому б(з)ь а) — это последняя вершина пути (дь а), Л(дь сз) — выходная буква, написанная на последнем ребре пути (дь сз), а отображение З(дь а) — слово, образованное й выходньзмн буквами, написанными на я ребрах этого пути.
Пример 8.2. Для автомата 5 из примера 8.1 8(дь ззьпз) б(Ч2 пзпз) =Ч31 б(чз, пзпзп!) =з)з1 Л(чз, пзпз) =~~2~ Л(дз, азаз) =об Л(дз, азазаз) =он Заметим, что б(о„азаз) = = б(за, азаз), но Л(дз, пза1) чьЛ(дз, азаз). Далее 5(дз, азаз) =озвз, 5(дз, азазаз) =озпзоь что иллюстрирует свойство 2 автоматного отображения. Состояние ду называется достижимьии из состояния дь если существует входное слово а, такое, что-6(дн а) =д;. Автомат Я называется сильно связяьзм, если из любого его состояния достижимо любое другое состояние. Автомат называется автономным, если его входной алфавит состоит из одной буквы: Л=(а). Все входные слова автономного автомата имеют вид аа...а.
Теорема 8.1. Любое достаточно длинное выходное слово автономного автомата с и состояниями является периодическим (возможно, с предпериодом), причем длины периода и предпериода не превосходят и; иначе говоря, оио имеет вид оьзьз... ыыь где ьзз — начальный отрезок ьз; при этом О<(сг)<а; 1((ьз)<п. Действительно, так как в графе автономного автомата из каждой вершины выходит только одно ребро, то его сильно связные подграфы могут быть только простыми циклами, из которых нет выходящих ребер. Поэтому в компоненте связности может быть только один цикл; остальные подграфы компоненты — зто деревья, подвешенные к циклу и ориентированные в его сторону. П Пример 8.3. Граф автомата, заданного в табл. 8.2, изображен на рис.
8.2 (входные буквы на ребрах опущены; выходной алфавит (~=(0, 1, 2)). Тиблияа дл 3,0 4,0 4,0 7,0 4,2 6,0 6,! 9,0 9,! Рис, а2 Здесь и в дальнейшем символы состояний для кратности обозначений будут заменяться их индексами. Изоморфизм и эквивалентность автоматов. Пусть 5= (Аз, !;!з (лз, бв Лз) и Т=(Аг, Яг, (лт, Ьт, Лг) — два автомата. Тройка отображений 7! Аз-л-Аг, д: (,!4-~.(!г, Лч )'з- Рг называется гомоморфизмом автомата 5 в автомат Т, если длЯ любых па=Аз, денЯз, пан)гз выполнены УсловиЯ !ср. (2.1)1: Ьг(й(д), 7(а)) =д(б (д, а)); (8.4) Автомат Т называется гомоморфным автомату 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
