В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 12
Текст из файла (страница 12)
Пусть M = (Q, Σ, D, q0 , F ) — детерминированный конечный автомат, допускающий L, т. е. L(M ) = L и k = |Q|. Пусть w ∈ Lи |w| > k . Рассмотрим последовательность конфигураций, которые проходитавтомат M , допуская цепочку w. Так как в ней по крайней мере k + 1конфигураций, то среди первых k + 1 конфигураций найдутся две различныес одинаковыми состояниями. Таким образом, получаем существование такойпоследовательности тактов, что(q0 , xyz) |− ∗ (q1 , yz) |− r (q1 , z) |− ∗ (q2 , e)для некоторых q1 ∈ Q, q2 ∈ F и 0 < r 6 k . Поскольку число конфигураций от начальной до (q1 , z) включительно не превосходит k + 1, а автоматдетерминированный, |xy| 6 k . Для любого i > 0 автомат может проделатьпоследовательность тактов (q0 , xy i z) ⊢∗ (q1 , y i z) ⊢+ (q1 , y i−1 z) . .
. ⊢+ (q1 , yz) ⊢++(q1 , z)⊢∗ (q2 , e).Таким образом, xy i z ∈ L для всех i > 1. Случай i = 0, т. е. xy ∈ L, такжеочевиден.С помощью леммы о разрастании можно показать, что не является регулярным множеством язык L={0n 1n |n > 1}.Допустим, что L регулярен. Тогда для достаточно большого n слово 0n 1nможно представить в виде xyz , причем y 6= e и xy i z ∈ L для всех i > 0.
Еслиy ∈ 0+ или y ∈ 1+ , то xz = xy 0 z ∈/ L. Если y ∈ 0+ 1+ , то xyyz ∈/ L. Получилипротиворечие. Следовательно, L не может быть регулярным множеством.3.5.1. Построение детерминированного конечного автомата с минимальным числом состояний. Рассмотрим теперь алгоритм построения ДКАс минимальным числом состояний, эквивалентного данному ДКА [2].Пусть M = (Q, T , D, q0 , F ) — ДКА. Будем называть M всюду определенным, если D(q , a) 6= ∅ для всех q ∈ Q и a ∈ T .Лемма 3.5. Пусть M = (Q, T , D, q0 , F ) — ДКА, не являющийся всюдуопределенным. Тогда существует всюду определенный ДКА M ′ , такой,что L(M ) = L(M ′ ).Д о к а з а т е л ь с т в о . Рассмотрим автоматM ′ = (Q ∪ {q ′ }, T , D′ , q0 , F ),3.5.
Связь регулярных множеств, конечных автоматов и регулярных грамматик55где q ′ ∈/ Q — некоторое новое состояние, а функция D′ определяется следующим образом.1. Для всех q ∈ Q и таких a ∈ T , что D(q , a) 6= ∅, определить D′ (q , a) == D(q , a).2. Для всех q ∈ Q и таких a ∈ T , что D(q , a) = ∅, определить D′ (q , a) = q ′ .3. Для всех a ∈ T определить D′ (q ′ , a) = q ′ .Легко показать, что автомат M ′ допускает тот же язык, что и M .Приведенный ниже алгоритм получает на входе всюду определенный автомат. Если автомат не является всюду определенным, то его можно сделатьтаковым на основании только леммы 3.5.Алгоритм 3.4.
Построение ДКА с минимальным числом состояний.Вход. Всюду определенный ДКА M = (Q, T , D, q0 , F ).Выход. ДКА M ′ = (Q′ , T , D′ , q0′ , F ′ ), такой, что L(M ) = L(M ′ ) и M ′содержит наименьшее возможное число состояний.Метод. Выполнить шаги 1-5:1. Построить начальное разбиение Π множества состояний из двух групп:заключительные состояния Q и остальные Q − F , т. е. Π = {F , Q − F }.2.
Применить к Π следующую процедуру и получить новое разбиение Πnew :for (каждой группы G в Π){разбить G на подгруппы так, чтобысостояния s и t из G оказалисьв одной подгруппе тогда и только тогда,когда для каждого входного символа aсостояния s и t имеют переходы по aв состояния из одной и той же группы в Π;заменить G в Πnew на множество всехполученных подгрупп;}3. Если Πnew = Π, то полагаем Πres = Π и переходим к шагу 4, иначеповторяем шаг 2 с Π := Πnew .4.
Пусть Πres = {G1 , . . . , Gn }. Определим:Q′ = {G1 , . . . , Gn };q0′ = G, где группа G ∈ Q′ такова, что q0 ∈ G;F ′ = {G|G ∈ Q′ и G ∩ F 6= ∅};D′ (p′ , a) = q ′ , если D(p, a) = q , где p ∈ p′ и q ∈ q ′ .Таким образом, каждая группа в Πres становится состоянием новогоавтомата M ′ . Если группа содержит начальное состояние автомата M ,то эта группа становится начальным состоянием автомата M ′ .
Если группа содержит заключительное состояние M , то она становится56Глава 3. Лексический анализзаключительным состоянием M ′ . Отметим, что каждая группа Πres либосостоит только из состояний из F , либо не имеет состояний из F .Переходы определяются очевидным образом.5) Если M ′ имеет «мертвое» состояние, т. е. состояние, которое не являетсядопускающим и из которого нет путей в допускающие, то удалить егои связанные с ним переходы из M ′ . Удалить из M ′ также все состояния,не достижимые из начального.Пример 3.10.
Результат применения алгоритма 3.4 приведен на рис. 3.15.Рис. 3.15Пусть De (p, w) — расширенная функция переходов, которая определяетсярекурсивно:De (p, a) = D(p, a), De (p, wa) = D(De (p, w), a).Будем говорить, что состояния p и q эквивалентны, если для всех входных цепочек w состояние De (p, w) является допускающим тогда и только тогда, когда состояние De (q , w) — допускающее. Состояния De (p, w) и De (q , w)могут и не совпадать — лишь бы оба они были либо допускающими, либонедопускающими.Если два состояния p и q не эквивалентны друг другу, то будем говорить,что они различимы, или неэквивалентны, т. е. существует хотя бы однацепочка w, для которой одно из состояний De (p, w) и De (q , w) являетсядопускающим, а другое — нет.Для того чтобы найти эквивалентные состояния, нужно выявить все парыразличимых состояний.
Все пары различимых состояний можно найти представленным ниже алгоритмом. Те пары состояний, которые найти не удастся,будут эквивалентными. Алгоритм, который называется алгоритмом заполнения таблицы, состоит в рекурсивном обнаружении пар различимых состояний ДКА = (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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
