В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 11
Текст из файла (страница 11)
Пусть L — язык, допускаемый детерминированным конечным автоматомM =({q1 , . . . , qn }, T , D, q1 , F ).k множество всех слов x, таких, что D e (q , x) =Обозначим посредством Riji= qj и если De (qi , y) = qs для любой цепочки y — префикса x, отличного от xи e, то s 6 k .k есть множество всех слов, которые переводят коИными словами, Rijнечный автомат из состояния qi в состояние qj , не проходя ни через какоесостояние qs для s > k . Однако i и j могут быть больше k .k может быть определено рекурсивно следующим образом:Rij0 = {a|a ∈ T , D(q , a) = q },Rijij52Глава 3. Лексический анализk = Rk−1RijijSk−1k−1 ∗ k−1(Rkk) Rkj , где 1 6 k 6 n.Rikk означает, что для входной цепочки w , пеТаким образом, определение Rijреводящей M из qi в qj без перехода через состояния с номерами, бо́льшимиk, справедливо ровно одно из следующих двух утверждений.k−11) Цепочка w принадлежит Rij, т. е.
при анализе цепочки w автоматникогда не достигает состояний с номерами, бо́льшими или равными k .k−12) Цепочка w может быть представлена как w = w1 w2 w3 , где w1 ∈ Rikk−1 ∗(подцепочка w1 переводит M сначала в qk ), w2 ∈ (Rkk) (подцепочка w2переводит M из qk обратно в qk , не проходя через состояния с номерами,k−1(подцепочка w3 переводит Mбо́льшими или равными k ), w3 ∈ Rkjиз состояния qk в qj ) — рис.
3.14.jРис. 3.14Тогда L =регулярно.Sqj ∈FR1nj . Индукцией по k можно показать, что это множествоТаким образом, для всякого регулярного множества имеется конечныйавтомат, допускающий в точности это регулярное множество, и наоборот —язык, допускаемый конечным автоматом, есть регулярное множество.Рассмотрим теперь соотношение между теми языками, которые порождаются праволинейными грамматиками, и теми, которые допускаются конечными автоматами.Праволинейная грамматика G = (N , T , P , S) называется регулярной,если:1) каждое ее правило, кроме S → e, имеет вид либо A → aB , либо A → a,где A, B ∈ N , a ∈ T ;2) в том случае, когда S → e ∈ P , начальный символ S не встречаетсяв правых частях правил.Лемма 3.4. Пусть G — праволинейная грамматика.
Тогда существуетрегулярная грамматика G′ такая, что L(G) = L(G′ ).Д о к а з а т е л ь с т в о предоставляется читателю в качестве упражнения.3.5. Связь регулярных множеств, конечных автоматов и регулярных грамматик53Теорема 3.4. Пусть G = (N , T , P , S) — праволинейная грамматика. Тогда существует недетерминированный конечный автомат M == (Q, T , D, q0 , F ) для которого L(M ) = L(G).Д о к а з а т е л ь с т в о . На основании леммы 3.4 без ограничения общности можно считать, что G — регулярная грамматика.Построим НКА M следующим образом:1) состояниями M будут нетерминалы G плюс новое состояние R, не принадлежащее N , так что Q = N ∪ {R};2) в качестве начального состояния M примем S , т.
е. q0 = S ;3) если P содержит правило S → e, то F = {S , R}, иначе F = {R} (напомним, что S не встречается в правых частях правил, если S → e ∈ P );4) состояние R ∈ D(A, a), если A → a ∈ P ; кроме того, D(A, a) содержитвсе B , такие, что A → aB ∈ P , причем D(R, a) = ∅ для каждого a ∈ T .Читая вход w, M моделирует вывод w в грамматике G. Покажем, чтоL(M ) = L(G). Пусть w = a1 a2 .
. . an ∈ L(G), n > 1. Тогда S ⇒ a1 A1 ⇒⇒ . . . ⇒ a1 a2 . . . an−1 An−1 ⇒ a1 a2 . . . an−1 an для некоторой последовательности нетерминалов A1 , A2 , . . . , An−1 . По определению, D(S , a1 ) содержит A1 ,D(A1 , a2 ) содержит A2 , и т. д., D(An−1 , an ) содержит R. Значит, w ∈ L(M ),поскольку De (S , w) содержит R, а R ∈ F . Если e ∈ L(G), то S ∈ F , так чтоe ∈ L(M ).Аналогично, если w = a1 a2 .
. . an ∈L(M ), n > 1, то существует последовательность состояний S , A1 , A2 , . . . , An−1 , R, такая, что D(S , a1 ) содержит A1 ,D(A1 , a2 ) содержит A2 , и т. д. Поэтому S ⇒ a1 A1 ⇒ a1 a2 A2 ⇒ . . . ⇒ a1 a2 . . .. . . an−1 An−1 ⇒ a1 a2 . . . an−1 an — вывод в G и x ∈ L(G). Если e ∈ L(M ),то S ∈ F , так что S → e ∈ P и e ∈ L(G).Теорема 3.5. Для каждого недетерминированного конечного автомата M = (Q, T , D, q0 , F ) существует праволинейная грамматика G == (N , T , P , S), такая, что L(G) = L(M ).Д о к а з а т е л ь с т в о .
Без потери общности можно считать, что автомат M — детерминированный. Определим грамматику G следующим образом:1) нетерминалами грамматики G будут состояния автомата M , так чтоN = Q;2) в качестве начального символа грамматики G примем q0 , т. е. S = q0 ;3) A → aB ∈ P , если D(A, a) = B ;4) A → a ∈ P , если D(A, a) = B и B ∈ F ;5) S → e ∈ P , если q0 ∈ F .Доказательство того, что S ⇒ ∗ w тогда и только тогда, когда De (q0 , w) ∈∈ F , аналогично доказательству теоремы 3.2.54Глава 3. Лексический анализВ некоторых случаях для определения того, является ли язык регулярным, может быть полезным необходимое условие, которое называется леммойОгдена о разрастании.Теорема 3.6. (Лемма о разрастании для регулярных множеств.) ПустьL — регулярное множество. Тогда существует такая константа k , чтоесли w ∈ L и |w| > k , то цепочку w можно представить в виде xyz , где0 < |y|, |xy| 6 k и xy i z ∈ L для всех i > 0.Д о к а з а т е л ь с т в о .
Пусть 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) являетсядопускающим, а другое — нет.Для того чтобы найти эквивалентные состояния, нужно выявить все парыразличимых состояний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
