Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
Abba Cba Ba C S Эта последовательность не что иное, как обращение (правого) вывода цепочки abba в грам- матике G. Она соответствует построению дерева снизу вверх (см. рис. 5). b b a a S S b b a a A S b b a a A C S b b a a A C B S b b a a A C B C S b b a a A C B C Рис. 5. Построение дерева вывода снизу вверх. Разбор по праволинейной грамматике По диаграмме состояний (см. рис. 4) построим праволинейную автоматную граммати- ку G right следующим способом: нетерминалами будут состояния из ДС (кроме S ); каждой дуге из состояния V в заключительное состояние S (помеченной признаком конца ) будет соответствовать правило V → ; каждой дуге из состояния V в состояние W, помеченной символом t, будет соответ- ствовать правило V → tW; начальное состояние H объявляется начальным символом грамматики 14) 14) Нетрудно описать и обратный алгоритм для праволинейной автоматной грамматики, если все ее правила с односимвольной правой частью имеют вид V → . Состояниями ДС будут нетерминалы грамматики и еще одно специальное заключительное состояние S, в которое для каждого правила вида V → проводится дуга Элементы теории трансляции / Разбор по регулярным грамматикам 28 G right {a, b, }, {H, A, B, C}, P, H P: H → aA | bB A → bC C → bB | aA | B → aC Заметим, что L(G right ) L(G left ), так как грамматики G right и G left соответствуют одной и той же ДС (см. рис. 4). Рассмотрим разбор цепочки abba по праволинейной грамматике G right . Последова- тельность переходов в ДС для этой цепочки такова: S C B C A H a b b a Каждый переход, за исключением последнего, означает теперь замену в сентенциальной форме нетерминала на пару «терминал-нетерминал» с помощью некоторого правила вывода грамматики G right . В результате получаем следующий (левый) вывод, который соответствует последовательности переходов в ДС: H aA abC abbB abbaC abba Такой вывод отражает построение дерева вывода сверху вниз (см. рис. 6). H b b a a H b b a a A H b b a a C A H b b a a B C A H b b a a C B C A H b b a a C B C A Рис. 6. Построение дерева вывода сверху вниз. О недетерминированном разборе При анализе по леволинейной грамматике может оказаться, что несколько нетермина- лов имеют одинаковые правые части, и поэтому неясно, к какому из них делать свертку (см. ситуацию 4 в описании алгоритма). При анализе по праволинейной грамматике может ока- из V, помеченная признаком конца . Для каждого правила вида V → t W проводится дуга из V в W, поме- ченная символом t. Начальнымсостоянием в ДС будет начальный символ H. Элементы теории трансляции / Разбор по регулярным грамматикам 29 заться, что нетерминал имеет две правые части с одинаковыми терминальными символами и поэтому неясно, на какую альтернативу заменить нетерминал. В терминах диаграммы состо- яний эти ситуации означают, что из одного состояния выходит несколько дуг, ведущих в разные состояния, но помеченных одним и тем же символом. Например, для грамматики G {a, b, }, {S, A, B}, P, S , где P: S → A A → a | Bb B → b | Bb разбор будет недетерминированным (т.к. у нетерминалов A и B есть одинаковые правые ча- сти — Bb). Такой грамматике будет соответствовать недетерминированный конечный автомат. Определение: недетерминированный конечный автомат (НКА) — это пятерка K, T, , H, S , где K — конечное множество состояний; T — конечное множество допустимых входных символов; — отображение множества K T в множество подмножеств K; H K — конечное множество начальных состояний; S K — конечное множество заключительных состояний. (A, t) {B 1 , B 2 ,..., B n } означает, что из состояния A по входному символу t можно осуще- ствить переход в любое из состояний B i , i 1, 2, ..., n. Также как и ДКА, любой НКА можно представить в виде таблицы (в одной ячейке такой таблицы можно указывать сразу несколь- ко состояний, в которые возможен переход из заданного состояния по текущему символу) или в виде диаграммы состояний (ДС). В ДС каждому состоянию из множества K соответ- ствует вершина; из вершины A в вершину B ведет дуга, помеченная символом t, если B (A, t). (В НКА из одной вершины могут исходить несколько дуг с одинаковой помет- кой). Успешный путь — это путь из начальной вершины в заключительную; пометка пути — это последовательность пометок его дуг. Язык, допускаемый НКА, — это множество по- меток всех успешных путей. Если начальное состояние автомата (НКА или ДКА) одновременно является и заклю- чительным, то автомат допускает пустую цепочку Замечание Автомат, построенный по регулярной грамматике без пустых правых частей, не допускает Для построения разбора по регулярной грамматике в недетерминированном случае можно предложить алгоритм, который будет перебирать все возможные варианты сверток (переходов) один за другим; если цепочка принадлежит языку, то будет найден успешный путь; если каждый из просмотренных вариантов завершится неудачей, то цепочка языку не принадлежит. Однако такой алгоритм практически неприемлем, поскольку при переборе ва- риантов мы, скорее всего, снова окажемся перед проблемой выбора и, следовательно, будем иметь «дерево отложенных вариантов» и экспоненциальный рост сложности разбора. Один из наиболее важных результатов теории конечных автоматов состоит в том, что класс языков, определяемых недетерминированными конечными автоматами, совпадает с классом языков, определяемых детерминированными конечными автоматами. Элементы теории трансляции / Разбор по регулярным грамматикам 30 Утверждение 10. Пусть L — формальный язык. Следующие утверждения эквива- лентны: (1) L порождается регулярной грамматикой; (2) L допускается ДКА; (3) L допускается НКА. Эквивалентность пунктов (1) и (2) следует из рассмотренных выше алгоритмов по- строения конечного автомата по регулярной грамматике и обратно — грамматики по автома- ту. Очевидно, что из (2) следует (3): достаточно записать вместо каждого перехода ДКА (C, a) b эквивалентный ему переход в НКА (C, a) {b}, начальное состояние ДКА по- местить в множество начальных состояний НКА, а заключительное состояние ДКА поме- стить в множество заключительных состояний НКА. Приводимый ниже алгоритм построе- ния ДКА, эквивалентного НКА, обосновывает то, что из (3) следует (2). Алгоритм построения ДКА по НКА Вход: НКА M K, T, , H, S Выход: ДКА M 1 K 1 , T, 1 , H 1 , S 1 , допускающий тот же язык, что и автомат М : L(M) L(M 1 ). Метод: 1. Элементами K 1 , т. е. состояниями в ДКА, будут некоторые подмножества множе- ства состояний НКА. Заметим, что в силу конечности множества K, множество K 1 также ко- нечно и имеет не более 2 s элементов, где s — мощность K. Подмножество {А 1 , A 2 , …, A n } состояний из К будем для краткости записывать как A 1 A 2 ...A n . Множество K 1 и переходы, определяющие функцию 1 , будем строить, начиная с состояния H 1 : H 1 A 1 A 2 ...A n , где А 1 , A 2 , …, A n H. Другими словами, все начальные состоя- ния НКА M объединяются в одно состояние H 1 для ДКА M 1 . Добавляем в множество K 1 по- строенное начальное состояние H 1 и пока считаем его нерассмотренным (на втором шаге оно рассматривается и строятся остальные состояния множества K 1 , а также переходы 1 .) 2. Пока в K 1 есть нерассмотренный элемент A 1 A 2 ...A m , «рассматриваем» его и выпол- няем для каждого t T следующие действия: Полагаем 1 ( A 1 A 2 ...A m , t ) B 1 B 2 ...B k , где для 1 j k в НКА (A i , t) B j для неко- торых 1 i m. Другими словами, B 1 B 2 ...B k — это множество всех состояний в НКА, куда можно перейти по символу t из множества состояний A 1 A 2 ...A m . В ДКА M 1 получается детерминированный переход по символу t из состояния A 1 A 2 ...A m в состояние B 1 B 2 ...B k . (Если k 0, то полагаем 1 ( A 1 A 2 ...A m , t ) ). Добавляем в K 1 новое состояние B 1 B 2 ...B k . Шаг 2 завершается, поскольку множество новых состояний K 1 конечно. 3. Заключительными состояниями построенного ДКА M 1 объявляются все состояния, содержащие в себе хотя бы одно заключительное состояние НКА M: S 1 : {A 1 A 2 ...A m | A 1 A 2 ...A m K 1 , A i S для некоторых 1 i m}. Замечание Множество S 1 построенного ДКА может состоять более, чем из одного элемента. Не для всех ре- гулярных языков существует ДКА с единственным заключительным состоянием (пример: язык всех цепочек в алфавите {a, b}, содержащих не более двух символов b). Однако для реализации Элементы теории трансляции / Разбор по регулярным грамматикам 31 алгоритма детерминированного разбора заключительное состояние должно быть единственным. В таком случае изменяют входной язык, добавляя маркер в конец каждой цепочки (на практике в роли маркера конца цепочки может выступать признак конца файла, символ конца строки или другие разделители). Вводится новое состояние S, и для каждого состояния Q из множества S 1 добавляется переход по символу : 1 (Q, ) S. Состояния из S 1 больше не считаются заклю- чительными, а S объявляется единственным заключительным состоянием. Теперь по такому ДКА можно построить автоматную грамматику, допускающую детерминированный разбор. Проиллюстрируемработуалгоритманапримерах. Пример 1. Задан НКА M { H, A, B, S }, {0, 1}, , {H }, {S } , где (H, 1) {B} (A, 1) {B, S} (B, 0) { A } L(M) { 1(01) n | n 1 }. Диаграмма для M изображена на рис.7. Рис. 7. ДС для автомата M. Грамматика, соответствующая M: S → A1 A → B0 B → A1 | 1 Построим ДКА по НКА, пользуясь предложенным алгоритмом. Начальным состояни- ем будет H. 1 (Н, 1) B 1 (B, 0) A 1 (A, 1) BS 1 (BS, 0) A Заключительным состоянием построенного ДКА является состояние BS. Таким образом, M 1 {H, B, A, BS }, {0, 1}, 1 , H, BS . Для удобства переименуем со- стояния в M 1 : BS обозначается теперь как S 1 , а в однобуквенных именах состояний вместо подчеркивания используется индекс 1. Тогда M 1 {H 1 , B 1 , A 1 , S 1 }, {0, 1}, { 1 (Н 1 , 1) B 1 ; 1 (B 1 , 0) A 1 ; 1 (A 1 , 1) S 1 ; 1 (S 1 , 0) A 1 }, H 1 , S 1 Грамматика, соответствующая M 1 : S 1 → A 1 1 A 1 → S 1 0 | B 1 0 B 1 → 1 Построим диаграмму состояний (рис. 8). H B S A 1 1 0 1 Элементы теории трансляции / Разбор по регулярным грамматикам 32 Рис. 8. Диаграмма состояний M 1 Пример 2. Дана регулярная грамматика G T, N, P, S P: S → Sb | Aa | a A → Aa | Sb | b, которой соответствует НКА. С помощью преобразования НКА в ДКА построить грамматику, по которой возможен детерминированный разбор. Решение Построим функцию переходов НКА: (H, a) {S} (H, b) {A} (A, a) {A, S} (S, b) {A, S} Процесс построения функции переходов ДКА удобно изобразить в виде таблицы, начав ее заполнение с начального состояния H, добавляя строки для вновь появляющихся состояний: символ состояние a b H S A S AS A AS AS AS AS Переходы ДКА: 1 (H, a) S 1 (H, b) A 1 (S, b) AS 1 (A, a) AS 1 (AS, a) AS 1 (AS, b) AS 1 0 1 0 H 1 B 1 A 1 S 1 появились сото- яния S и A , они рассматри- ваются в следу- ющих строках таблицы Элементы теории трансляции / Разбор по регулярным грамматикам 33 Переобозначим сотояния: A A, H H, AS Y, S X. Два заключительных состояния X и Y сведем в одно заключительное состояние S, используя маркер конца цепоч- ки . После такой модификации получаем ДКА с единственным заключительным состояни- ем S и функцией переходов: 1 (H, a) X 1 (H, b) A 1 (X, b) Y 1 (X, ) S 1 (A, a) Y 1 (Y, a) Y 1 (Y, b) Y 1 (Y, ) S По ДКА строим грамматику G 1 , позволяющую воспользоваться алгоритмом детерми- нированного разбора: G 1 : S → X | Y Y → Ya | Yb | Aa | Xb X → a A → b В заключение раздела о регулярных языках приведем пример использования автома- тов в решении теоретических задач. |