В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 12
Текст из файла (страница 12)
Все пары различимых состояний можно найти представленным ниже алгоритмом. Те пары состояний, которые найти не удастся,будут эквивалентными. Алгоритм, который называется алгоритмом заполнения таблицы, состоит в рекурсивном обнаружении пар различимых состояний ДКА = (Q, Σ, D, q0 , F ).Базис. Если состояние p — допускаюшее, а q — не допускающее, то парасостояний (p, q) различима.Индукция.
Пусть p и q — состояния, для которых существует входнойсимвол a, приводяший их в различимые состояния r = D(p, a) и s = D(q , a).3.5. Связь регулярных множеств, конечных автоматов и регулярных грамматик57Тогда (p, q) — пара различимых состояний. Это очевидно, потому что если rи s различимы, то должна существовать цепочка w, отличающая r от s. Тогдацепочка w отличает p от q , так как De (r, aw) и De (s, aw) — это та же парасостояний, что и De (r, w) и De (s, w).Пример 3.11.
Рассмотримна рис. 3.16.вкачествепримераавтомат,изображенныйРис. 3.16Построим матрицу эквивалентности состояний.Базис. Все пары незаключительных состояний не эквивалентны паре (B , D).В пару (D, E) по символу b ведут, соответственно, множества {C} и {A, B , D, E},что делает неэквивалентными пары (C , E) и (C , A). В пару (B , E) по символу aведут, соответственно, множества {A} и {E , C}, что делает неэквивалентными пары(A, E) и (C , A). Результат представлен в табл. 3.3.Т а б л и ц а 3.3D xC x xB x 0xA x x x xE D C BТаким образом, состояния D и B эквивалентны.Теорема 3.7.
Если два состояния не различаются с помощью алгоритма заполнения таблицы, то они эквивалентны.Д о к а з а т е л ь с т в о . Снова рассмотрим ДКА A = (Q, Σ, D, q0 , F ).Предположим, что утверждение теоремы неверно, т. е. существует хотя быодна пара состояний (p, q), для которой выполняются следующие условия:58Глава 3. Лексический анализ1) состояния p и q различимы, т. е. существует некоторая цепочка w,для которой только одно из состояний De (p, w) и De (q , w) являетсядопускающим;2) алгоритм заполнения таблицы не может обнаружить, что состояния rи s различимы.Назовем такую пару состояний плохой парой.Если существуют плохие пары, то среди них должны быть такие, которыеразличимы с помощью кратчайших из всех цепочек, различающих плохие пары.
Пусть плохая пара (p, q) такова, что для нее w = a1 a2 . . . an — кратчайшаяиз всех цепочек, различающих плохие пары. Тогда только одно из состоянийDe (p, w) и De (q , w) является допускаюшим.Заметим, что цепочка w не может быть e, так как если некоторая парасостояний различается с помощью e, то ее можно обнаружить, выполнивбазисную часть алгоритма заполнения таблицы. Следовательно, n > 1.Рассмотрим состояния r = D(p, a1 ) и s = D(q , a1 ).
Эти состояния можноразличить с помощью цепочки a2 a3 . . . an , поскольку она переводит r и sв состояния De (p, w) и De (q , w). Однако тогда цепочка, отличающая r отs, короче любой цепочки, различающей плохую пару. Следовательно, (r, s)не может быть плохой парой, и алгоритм заполнения таблицы должен былобнаружить, что эти состояния различимы.Но индуктивная часть алгоритма заполнения таблицы не остановится,пока не придет к выводу, что состояния p и q также различимы, посколькууже обнаружено, что состояние D(p, a1 ) = r отличается от D(q , a1 ) = s. Получено противоречие с предположением о том, что существуют плохие парысостояний. Но если плохих пар нет, то любую пару различимых состоянийможно обнаружить с помощью алгоритма заполнения таблицы, и теоремадоказана.3.5.2.
Проверка эквивалентности регулярных языков. Эквивалентность регулярных языков легко проверяется с помощью алгоритма заполнениятаблицы. Предположим, что языки L и M представлены, например, соответственно регулярным выражением и некоторым НКА. Преобразуем каждоеиз этих представлений в ДКА. Теперь представим себе ДКА, множествосостояний которого равно объединению множеств состояний автоматов дляязыков L и M . Технически этот ДКА содержит два начальных состояния,но фактически при проверке эквивалентности начальное состояние не играетникакой роли, поэтому любое из этих двух состояний можно принять за единственное начальное.Далее проверяем эквивалентность начальных состояний двух заданныхДКА, используя алгоритм заполнения таблицы. Если они эквивалентны,то L = M , а если нет, то L 6= M .3.5.
Связь регулярных множеств, конечных автоматов и регулярных грамматик59Пример 3.12. Рассмотрим регулярное выражение a(ab)∗. Построим по немудетерминированный конечный автомат двумя способами:1) сначала построив промежуточный недерминированный конечный автомат;2) построив алгоритмом прямого построения ДКА по регулярному выражению.В первом случае получим автомат, изображенный на рис. 3.17, во втором —изображенный на рис. 3.16 (в обоих случаях автоматы пополнены мертвымсостоянием).Рис.
3.17Можно считать, что на рис. 3.16 и 3.17 изображен один ДКА, содержащий девятьсостояний от A до E и от 0 до 3. Если применить алгоритм заполнения таблицык этому автомату, то в результате получим таблицу различимости (табл. 3.4).Т а б л и ц а 3.43 xx 0x x2 x0 x0 x1 0x x x x0 xx x x 0A B C D EПоскольку в результате проверки установлено, что состояния A и 1 эквивалентныи являются начальными у двух заданных автоматов, делаем вывод, что эти ДКАдействительно допускают один и тот же язык.Время заполнения таблицы, а значит, и время проверки эквивалентностидвух состояний, полиномиально относительно числа состояний. Если числосостояний равно n, то количество пар состояний равно Cn2 , или n(n − 1)/2.За один цикл рассматриваются все пары состояний, чтобы определить, является ли одна из пар состояний-преемников различимой.
Значит, один циклзанимает время не больше O(n2 ). Кроме того, если в некотором цикле60Глава 3. Лексический анализне обнаружены новые пары различимых состояний, то алгоритм заканчивается. Следовательно, количество циклов не превышает O(n2 ), а верхняя границавремени заполнения таблицы равна O(n4 ).Однако с помощью более аккуратно построенного алгоритма можно заполнить таблицу за время O(n2 ). С этой целью для каждой пары состояний (r, s)необходимо составить список пар состояний (p, q), «зависящих» от (r, s), т. е.если пара (r, s) различима, то (p, q) также различима.
Вначале такие спискисоздаются путем рассмотрения каждой пары состояний (p, q), и для каждоговходного символа (а их число фиксировано) пара (p, q) вносится в списокдля пары состояний-преемников (D(p, a) и D(q , a)).Если обнаруживается, что пара (r, s) различима, то в списке этой парыкаждая пока неразличимая пара отмечается как различимая и помещаетсяв очередь пар, списки которых нужно проверить аналогичным образом.Общее время работы этого алгоритма пропорционально сумме длин списков, так как каждый раз проверяется наличие некоторой пары в списке (когдапроходим по списку пары, признанной различимой). Так как размер входногоалфавита считается постоянным, то каждая пара состояний попадает в O(1)списков.
Поскольку всего пар O(n2 ), суммарное время также O(n2 ).Еще одним важным следствием проверки эквивалентности состоянийявляется возможность минимизации ДКА. Это значит, что для каждогоДКА можно найти эквивалентный ему ДКА с наименьшим числом состояний. Более того, для данного языка существует единственный минимальный(с точностью до обозначения состояний).
Основная идея минимизации ДКАсостоит в том, что понятие эквивалентности состояний позволяет объединятьсостояния в блоки следующим образом.1.2.3.4.Все эквивалентные состояния и только они образуют блок.Затем строим ДКА с состояниями — блоками.Переходы определяем естественным образом.Начальным состоянием является блок, содержащий начальное состояние исходного автомата.5. Заключительным состоянием является блок, содержащий заключительные состояния исходного автомата.Доказательство основано на том, что эквивалентность состояний транзитивна, а кроме того, по определению симметрична и рефлексивна; значит,блоки состояний образуют разбиение.Теорема 3.8.
ДКА, полученный в результате применения алгоритмаминимизации, имеет наименьшее возможное число состояний из всехДКА, эквивалентных данному.Д о к а з а т е л ь с т в о . Пусть N — ДКА, эквивалентный исходному M ,но имеющий меньшее число состояний. Применим алгоритм определения3.5.
Связь регулярных множеств, конечных автоматов и регулярных грамматик61эквивалентных неразличимых состояний к объединению M и N . Их начальные состояния эквивалентны (неразличимы). Для любых двух неразличимыхсостояний p и q все их (непосредственные) преемники по любому символунеразличимы, поскольку если бы преемники были различимы, то p и qможно было бы различить. Таким образом, каждое состояние p автоматаM неотличимо хотя бы от одного состояния q автомата N . В самом деле,существует цепочка a1 , .
. . , ak , переводящая M из начального состояния в p.Эта же цепочка переводит N в некоторое q . Это следует из того, что начальные состояния неразличимы, и из предыдущего замечания. Если |M | > |N |,то в M имеются два состояния, неразличимые с некоторым q из M . Но этопротиворечит построению M , в котором все состояния различимы.Следствие. Между состояниями любых двух минимальных для данногоДКА автоматов можно установить взаимно однозначное соответствие,т.
е. эти автоматы эквивалентны с точностью до именования состояний.Д о к а з а т е л ь с т в о . Достаточно применить предыдущее рассуждение в обе стороны.Таким образом, получаем следующий алгоритм минимизации автомата.1. Создать все пары (заключительное состояние, незаключительное состояние) и отметить их как непомеченные.2. Пока есть непомеченная пара:а) пометить ее;б) для каждой пары состояний, ведущей в данную пару по каждому(одному и тому же) символу: если эта пара не обозначена какразличимая, сделать ее различимой и непомеченной;в) построить множества эквивалентных состояний как транзитивноезамыкание, каждое такое множество объявить состоянием;г) множества, состоящие из заключительных состояний, сделать заключительными.Если применить этот алгоритм к автомату, изображенному на рис. 3.16,то получим автомат, изображенный на рис.
3.17, поскольку состояния B и Dэквивалентны. Если применить этот алгоритм одновременно к автоматам,изображенным на рис. 3.16 и 3.17, то получим, что эквивалентными являютсямножества состояний {1, A}, {3, C}, {2, B , D} и {0, E}.3.5.3. Реализация на Java. Программа на Java минимизации ДКАс проверкой эквивалентности двух ДКА приведена в пакете Finite (программное приложение). Функция equivalence() делает следующее.62Глава 3. Лексический анализ1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
