В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 9
Текст из файла (страница 9)
Конечные автоматы39Пусть M = (Q, T , D, q0 , F ) — НКА. Будем называть M детерминированным конечным автоматом (ДКА), если выполняются следующие дваусловия:1) D(q , e) = ∅ для любого q ∈ Q;2) D(q , a) содержит не более одного элемента для любых q ∈ Q и a ∈ T .Так как функция переходов ДКА содержит не более одного элемента длялюбой пары аргументов, для ДКА мы будем пользоваться записью D(q , a)=pвместо D(q , a)={p}.Конечный автомат может быть изображен графически в виде диаграммы,представляющей собой ориентированный граф, в котором каждому состояниюсоответствует вершина, а дуга, помеченная символом a ∈ T ∪ {e}, соединяетдве вершины p и q , если p ∈ D(q , a).
На диаграмме выделяются начальноеи заключительные состояния (в примерах ниже — соответственно входящейстрелкой и двойным контуром).Пример 3.3. Пусть L = L(r), где r = (a|b)∗ a(a|b)(a|b).а) Недетерминированный конечный автомат M , допускающий язык L:M = {{1, 2, 3, 4}, {a, b}, D, 1, {4}},где функция переходов D определяется так:D(1, a) = {1, 2}, D(3, a) = {4},D(1, b) = {1},D(2, b) = {3},D(2, a) = {3},D(3, b) = {4}.Диаграмма автомата приведена на рис.
3.3, а.б) Детерминированный конечный автомат M , допускающий язык L:M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}},где функция переходов D определяется так:D(1, a) = 2,D(1, b) = 1,D(2, a) = 4,D(2, b) = 7,D(3, a) = 3,D(3, b) = 5,D(4, a) = 3,D(4, b) = 5,D(5, a) = 8,D(5, b) = 6,D(6, a) = 2,D(6, b) = 1,D(7, a) = 8,D(7, b) = 6,D(8, a) = 4,D(8, b) = 7.Диаграмма автомата приведена на рис. 3.3, б.Пример 3.4.
Диаграмма автомата, допускающего множество чисел в десятичнойзаписи, приведена на рис. 3.4.40Глава 3. Лексический анализРис. 3.3Рис. 3.4Пример 3.5. Анализ цепочек.а) При анализе цепочки w = ababa автомат из примера 3.3, а может сделатьследующую последовательность тактов:(1, ababa) ⊢ (1, baba) ⊢ (1, aba) ⊢ (2, ba) ⊢ (3, a) ⊢ (4, e).Состояние 4 является заключительным, следовательно, цепочка w допускаетсяэтим автоматом.б) При анализе цепочки w = ababab автомат из примера 3.3, б должен сделатьследующую последовательность тактов:(1, ababab) ⊢ (2, babab) ⊢ (7, abab) ⊢ (8, bab) ⊢ (7, ab) ⊢ (8, b) ⊢ (7, e).Так как состояние 7 не является заключительным, цепочка w не допускаетсяэтим автоматом.3.3.
Интерпретатор НКА на JavaВ пакете Automata рассматривается реализация интерпретатора конечных автоматов. Если интерпретация детерминированного конечного автоматадостаточно очевидна, то интерпретация недетерминированного конечного автомата требует некоторых пояснений. Недетерминизм в определении НКАозначает следующее: из данной конфигурации НКА могут быть порожденынесколько новых.
Таким образом, мы имеем дерево возможных конфигураций3.4. Алгоритмы построения конечных автоматов41НКА на данном входе. Поскольку в общем случае НКА может иметь e-переходы, которые могут образовывать циклы на графе автомата, то деревоконфигураций на данном входе, вообще говоря, бесконечно.
Автомат допускает, если среди этих конфигураций есть допускающая. Таким образом,возникает вопрос о сведении потенциально бесконечного множества конфигураций к некоторому конечному, которое нужно просмотреть, чтобы убедиться,допускает ли НКА строку или нет. С другой стороны, ясно, что количестворазличных конфигураций НКА на данном входе длины n не превосходитn ∗ |Q|, где Q — множество состояний.Основные структуры данных в программе — это две функции. Однаиз них — HashMap TransitionFunction — отображает состояния в отображения HashMap SymbolToState — для каждого символа в данном состоянии, длякоторого определен переход; значением этой функции является множествосостояний, в которые возможен переход по данному символу (включая e).Основной цикл составляет просмотр списка конфигураций LinkedList configurations.
Вначале этот список состоит из одной начальной конфигурации. Затемвыбираем первый элемент этого списка, удаляем его из списка, определяемконфигурации, в которые можно попасть из данной по текущему символу,и включаем их в список. Для каждой конфигурации определяется число —длина непросмотренного входа, который надо прочитать из данного состояния. Если мы попадаем повторно в состояние и длина непросмотренноговхода не изменилась, то конфигурацию не надо включать в список непросмотренных конфигураций. Если попадаем в заключительную конфигурацию,то останавливаемся.3.4.
Алгоритмы построения конечных автоматов3.4.1. Построение недетерминированного конечного автомата по регулярному выражению. Рассмотрим алгоритм построения по регулярномувыражению недетерминированного конечного автомата, допускающего тотже язык.Алгоритм 3.1. Построение недетерминированного конечного автоматапо регулярному выражению.Вход. Регулярное выражение r в алфавите T .Выход.
НКА M , такой, что L(M ) = L(r).Метод. Автомат для выражения строится композицией из автоматов,соответствующих подвыражениям. На каждом шаге построения строящийсяавтомат имеет в точности одно заключительное состояние, в начальное состояние нет переходов из других состояний, и нет переходов из заключительногосостояния в другие.42Глава 3. Лексический анализ1. Для выражения ∅ строится автомат согласно рис. 3.5.Рис. 3.52.
Для выражения e строится автомат согласно рис. 3.6.Рис. 3.63. Для выражения a (a ∈ T ) строится автомат согласно рис. 3.7.Рис. 3.74. Пусть M (s) и M (t) — НКА для регулярных выражений s и t соответственно.а) Для выражения s|t автомат M (s|t) строится, как показанона рис. 3.8. Здесь i — новое начальное состояние и f — новоезаключительное состояние. Заметим, что имеет место переходпо e из i в начальные состояния M (s) и M (t) и переход по eиз заключительных состояний M (s) и M (t) в f . Начальноеи заключительное состояния автоматов M (s) и M (t) не являютсятаковыми для автомата M (s|t).iРис.
3.8б) Для выражения st автомат M (st) строится следующим образом(рис. 3.9).Начальное состояние автомата M (s) становится начальным длянового автомата, а заключительное состояние M (t) становитсязаключительным для нового автомата. Начальное состояние M (t)и заключительное состояние M (s) сливаются, т. е. все переходы3.4. Алгоритмы построения конечных автоматов43Рис.
3.9из начального состояния M (t) становятся переходами из заключительного состояния M (s). В новом автомате это объединенноесостояние не является ни начальным, ни заключительным.в) Для выражения s∗ автомат M (s∗ ) строится следующим образом(рис. 3.10):Рис. 3.10Здесь i — новое начальное состояние, а f — новое заключительноесостояние.3.4.2. Построение детерминированного конечного автомата по недетерминированному.
Рассмотрим алгоритм построения по недетерминированному конечному автомату детерминированного конечного автомата, допускающего тот же язык.В алгоритме будут использоваться следующие функции:e-closure(R) (R ⊆ Q) — множество состояний НКА, достижимых изсостояний, входящих в R, посредством только переходов по e, т. е. множество[S={p|(q , e) ⊢∗ (p, e)};q∈Rmove(R, a) (R ⊆ Q) — множество состояний НКА, в которые есть переходна входе a для состояний из R, т. е. множество[S={p|p ∈ D(q , a)}.q∈RФункция e-closure(R) вычисляется следующим простым алгоритмом.1. Внести все состояния из R в список list.2.
while (list не пуст) {выбрать первый элемент списка r и удалить его из списка;for (каждого состояния u c дугой от r в u, помеченной e)/ e − closure(R) ) {do if (u ∈добавить u к e-closure(R);поместить u в список list; } }44Глава 3. Лексический анализАлгоритм 3.2. Построение детерминированного конечного автоматапо недетерминированному.Вход. НКА M = (Q, T , D, q0 , F ).Выход. ДКА M ′ = (Q′ , T , D′ , q0′ , F ′ ), такой, что L(M ) = L(M ′ ).Метод.
Каждое состояние результирующего ДКА — это некоторое множество состояний исходного НКА.Вначале Q′ и D′ пусты. Выполнить шаги 1–4:1. Определить q0′ = e-closure({q0 }).2. Добавить q0′ в Q′ как непомеченное состояние.3. Выполнить следующую процедуру:while (в Q′ есть непомеченное состояние R){пометить R;for (каждого входного символа a ∈ T ){S = e-closure(move(R, a));if (S 6= ∅){/ Q′ )if (S ∈добавить S в Q′ как непомеченноесостояние;определить D′ (R, a) = S ;}}}4.
Определить F ′ = {S|S ∈ Q′ , S ∩ F 6= ∅}.Пример 3.6. Результат применения алгоритма 3.2 приведен на рис. 3.11.Рис. 3.113.4. Алгоритмы построения конечных автоматов453.4.3. Реализация на Java. Алгоритм преобразования недерминированного конечного автомата в детермининрованный реализован в пакете Automata функцией NFAtoDFA(). Две основные структуры данных — это функция,отображающая имя состояния (номер) в подмножество состояний исходногоНКА, образующих данное состояние ДКА, и список непомеченных состояний. Очередное состояние выбирается из списка непомеченных состояний.Когда в результате работы функции move формируется новое подмножество,оно проверяется на совпадение с каким-либо из имеющихся.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
