1 Глава 3. Конечные автоматы и регулярные грамматики Теория формальных языков и трансляций

2 § 3.1. Конечный автомат Определение 3.1. Конечным автоматом называется формальная система M = (Q, Σ, δ, q 0, F), где Q конечное непустое множество состояний; Σ конечный входной алфавит; δ отображение типа Q Σ Q; q 0 Q начальное состояние; Слайд 33Слайд 33 F Q множество конечных состояний. Слайд 33

3 Запись δ(q, a) = p, где q, p Q и a Σ, означает, что конечный автомат M в состоянии q, сканируя входной символ a, продвигает свою входную головку на одну ячейку вправо и переходит в состояние p. Конечный автомат Область определения отображения δ можно расширить до Q Σ * следующим образом: δ (q, ) = q, δ (q, xa) = δ (δ (q, x), a) для любого x Σ * и a Σ.

4 Конечный автомат Таким образом, запись δ (q, x) = p означает, что fa M, начиная в состоянии q Q чтение цепочки x Σ *, записанной на входной ленте, оказывается в состоянии p Q, когда его входная головка продвинется правее цепочки x. Далее мы будем использовать одно и то же обозначение δ для обоих отображений, так как это не приведёт к путанице.

5 δ(q 1, a 2 ) = q 2 Определенная таким образом модель конечного автомата называется детерми- нированной (см. рис. 3.0). Для обозначения детерминированного автомата часто используют аббревиатуру dfa (deterministic finite automaton). Конечный автомат a1a1 a2a2...aiai a i+1 δ : Q Σ Q q1q1 q0q0 δ(q 0, a 1 ) = q 1 a1a1 a2a2...aiai a i+1 a i+2... q2q2 Рис. 3.0.

6 Определение 3.2. Цепочка x Σ * принимается конечным автоматом M, если δ(q 0, x) = p для некоторого p F. Множество всех цепочек x Σ *, принимаемых конечным автоматом M, называется языком, распознаваемым конечным автоматом M, и обозначается как T(M), т. е. T(M) = {x Σ * δ(q 0, x) = p при p F}. Язык, распознаваемый конечным автоматом

7 Любое множество цепочек, принимае- мых конечным автоматом, называется регулярным. Язык, распознаваемый конечным автоматом

8 Пример 3.1. Пусть задан dfa M = (Q, Σ, δ, q 0, F), где Q = {q 0, q 1, q 2, q 3 }, Σ = {0, 1}, F = {q 0 }, δ(q 0, 0) = q 2, δ(q 0, 1) = q 1, δ(q 1, 0) = q 3, δ(q 1, 1) = q 0, δ(q 2, 0) = q 0, δ(q 2, 1) = q 3, δ(q 3, 0) = q 1, δ(q 3, 1) = q 2. Рассмотрим диаграмму переходов этого конечного автомата. Ret 14

9 q0q0 q1q1 q2q2 q3q Start Рис Диаграмма переходов

10 Диаграмма переходов конечного автомата состоит из узлов, представляющих состоя- ния, и ориентированных дуг, определяющих возможные переходы, которые зависят от входных символов. Так, если δ(q, a) = p, то из узла, представляющего состояние q, в узел, представляющий состояние p, проводится дуга, помеченная входным символом a. Двойным кружком выделено единствен- ное в данном примере конечное состояние, которое является одновременно и начальным. Диаграмма переходов

11 Предположим, что на входе автомата M находится цепочка Поскольку δ(q 0, 1) = q 1, а δ(q 1, 1) = q 0 и q 0 F, то цепочка 11 находится в языке, распоз- наваемом данным конечным автоматом M. Но мы интересуемся всей входной цепочкой. Сканируя остаток 0101 входной цепочки, автомат переходит последователь- но в состояния q 2, q 3, q 1, q 0. Поэтому δ(q 0, ) = q 0, и потому цепочка тоже находится в T(M). Диаграмма переходов

12 Очевидно, что T(M) есть множество всех цепочек из {0, 1} *, содержащих чётное число нулей и чётное число единиц. Вопрос: T(M)? Язык, распознаваемый конечным автоматом

13 § 3.2. Отношения эквивалентности и конечные автоматы Пусть M dfa. Определим отношение R на множестве Σ * следующим образом: (x, y) R тогда и только тогда, когда δ(q 0, x) = δ(q 0, y). Отношение R рефлексивно, симметрично и транзитивно, т. е. R отношение эквивалентности. Транзитивность: (x, y) R, (y, z) R (x, z) R: (q 0, x) = (q 0, y) = p; (q 0, y) = (q 0, z) = q = p (x, z) R

14 Автомат M из примера 3.1 индуцирует отношение эквивалентности R, которое делит множество {0, 1} * на четыре класса эквивалентности, соответствующие четы- рём состояниям этого автомата.примера 3.1 Кроме того, если xRy, то для всех z {0,1} * имеет место xzRyz, поскольку δ(q 0, xz) = δ(δ(q 0, x), z) = δ(δ(q 0, y), z) = = δ(q 0, yz). Такое отношение эквивалентности называется право-инвариантным. Отношения эквивалентности и конечные автоматы

15 Теорема 3.1. Следующие три высказывания эквивалентны: 1) Язык L * распознаётся некоторым fa. 2) Язык L есть объединение некоторых классов эквивалентности право-инвариантного отношения эквивалентности конечного индекса; 3) Пусть отношение эквивалентности R опреде- ляется через язык L следующим образом: xRy тогда и только тогда, когда для всех z * имеет место принадлежность xz L точно тогда, когда yz L. Отношение R имеет конечный индекс. Отношения эквивалентности и конечные автоматы Ret 25

16 Отношения эквивалентности и конечные автоматы Доказательство Предположим, что язык L принимается некоторым конечным автоматом = (,,,, ). Пусть отношение эквивалентности, определяемое следующим образом: тогда и только тогда, когда

Отношение R право-инвариантно, по- скольку, если xRy, т. е. то для любого z * имеем Индекс отношения R конечен, поскольку (самое большее) он равен числу состояний fa. т. е.

Кроме того, язык L есть объединение лишь тех классов эквивалентности, кото- рые включают цепочки x *, переводя- щие автомат в конечные состояния: где Итак, из высказывания (1) следует (2).

Пусть язык L есть объединение некоторых классов эквивалентности в отношении R, которое является право- инвариантным и имеет конечный индекс. Покажем сначала, что каждый класс эквивалентности R целиком содержится в некотором классе эквивалентности R, определённом в высказывнии (3). Отношения эквивалентности и конечные автоматы

20 Пусть xRy. Так как отношение R право- инвариантно, то для любого z * имеет место xzRyz и, таким образом, xz L точно тогда, когда yz L, т. е. x R y. Следовательно, R R, и потому [x] R [x] R. Это и значит, что любой класс эквивалентности отношения эквивалент- ности R содержится в некотором классе эквивалентности отношения эквивалент- ности R. 2 3

Поскольку отношения R и R разбивают на классы эквивалентности одно и то же множество цепочек *, то индекс отношения эквивалентности R не может быть больше индекса отношения эквивалентности R (чем крупнее классы, тем их меньше). Согласно высказыванию (2) индекс отношения эквивалентности R конечен. Следовательно, индекс отношения эквива- лентности R, тем более, конечен. Итак, из высказывания (2) следует (3).

Пусть xRy. Тогда для любых w, z * цепочка xwz L в точности тогда, когда цепочка ywz L. Следовательно, xwRyw, и потому R правоинвариантно. Построим конечный автомат M = (Q,, δ, q 0, F), где в качестве Q возьмем конечное множество классов эквивалентности R, т. е. Q = {[x] R x * }; Отношения эквивалентности и конечные автоматы Ret 25

23 положим δ([x] R, a) = [xa] R, и это определение непротиворечиво, так как R право-инвариантно; положим q 0 = [ ] R и F = {[x] R x L}. Очевидно, что конечный автомат M распознаёт язык L, поскольку δ(q 0, x) = δ([ ] R, x) = [x] R, и, таким образом, x T(M) тогда и только тогда, когда [x] R F. Итак, из высказывания (3) следует (1). 3 1

24 Теорема 3.2. Конечный автомат с минимальным числом состояний, распоз- нающий язык L, единствен с точностью до изоморфизма (т. е. переименования состояний), и есть fa M из теоремы 3.2 (см. 3 1). Конечный автомат с минимальным числом состояний

25 Доказательство. При доказательстве теоремы 3.1 мы установили, что любой конечный автомат теоремы 3.1 распознающий язык L, индуцирует отношение эквивалентности, индекс которого не меньше индекса отношения эквивалентности R, определённого при формулировке утверждения 3 1. Поэтому число состояний fa M больше или равно числу состояний fa M, построенного в третьей части доказательства теоремы 3.2.утверждения 3 1 Конечный автомат с минимальным числом состояний

26 Если M fa с минимальным числом состояний, то число его состояний равно числу состояний fa M и между состояниями M и M можно установить одно-однозначное соответствие. Конечный автомат с минимальным числом состояний

27 Конечный автомат с минимальным числом состояний Действительно, пусть Должна существовать некоторая цепочка x *, такая, что ибо в против- ном случае состояние без какого-нибудь ущерба для языка, распознаваемого этим автоматом, можно было бы исключить из множества состояний как недостижимое.

28 Отбросив такое недостижимое состояние, мы получили бы автомат с меньшим числом состояний, который распознавал бы всё тот же самый язык. Но это противоречило бы предположению, что M является конечным автоматом с мини- мальным числом состояний. Конечный автомат с минимальным числом состояний

29 Конечный автомат с минимальным числом состояний Пусть Сопоставим с состояние q Q, достижимое автоматом M по прочтении той же цепочки x: q = δ(q 0, x) = δ([ ] R, x) = [x] R. Это сопоставление является непротиворечи- вым, так как отображение R право-инвариантное. Действительно, если q,p и q =p, причём то их образы есть соответственно q = δ(q 0, x) = δ([ ] R, x) = [x] R и p = δ(q 0, y)= δ([ ] R, y) = [y] R. а

30 Учитывая, что x и y принадлежат одному и тому же классу эквивалентности отношения, и что, заключаем, что x и y также находятся в одном и том же классе эквивалентности отношения R, т. е. [x] R = [y] R, и потому q = p. Другими словами, если прообразы состояний (q и p ) равны, то равны и их образы (q и p). Конечный автомат с минимальным числом состояний

31 Конечный автомат с минимальным числом состояний a a x xaxa Рис. 3.2.

32 Кроме того, если fa M совершает переход из состояния q в состояние p, прочитав символ a, то fa M переходит из состояния q, являющегося образом q, в состояние p, являющееся образом p, прочитав тот же самый символ a, так как δ([x] R, a) = [xa] R (рис. 3.2).рис. 3.2 Это и значит, что мы имеем изоморфное отображение множества состояний fa M на множество состояний fa M. Конечный автомат с минимальным числом состояний

33 § 3.3. Недетерминированные конечные автоматы Теперь мы введём понятие недетерми- нированного конечного автомата (ndfa nondeterministic finite automaton). От своего детерминированного аналога, определённого ранее (см. опр. 3.1), он отличается только типом управляющего отображения δ.3.1 Когда важно подчеркнуть, что имеется в виду именно детерминированная модель конечного автомата, мы будем использовать обозначение dfa, а когда это не важно, будем использовать нейтральное fa.

34 Мы увидим, что любое множество, распозна- ваемое недетерминированным конечным автома- том, может также распознаваться детерминиро- ванным конечным автоматом. Недетерминированный конечный автомат является полезным понятием при доказательстве теорем. Кроме того, с этого простейшего понятия легче начать знакомство с недетерминированными устройствами, которые не эквивалентны своим детерминированным аналогам. Недетерминированные конечные автоматы

35 Определение 3.6. Недетерминированным конечным автоматом называется фор- мальная система M = (Q, Σ, δ, q 0, F), где Q конечное непустое множество состояний; Σ входной алфавит; δ отображение типа Q Σ 2 Q, q 0 Q начальное состояние; F Q множество конечных состояний. Недетерминированные конечные автоматы

36 Существенная разница между детер- минированной и недетерминированной моделями конечного автомата состоит в том, что значение δ(q,a) является (возможно пустым) множеством состояний, а не одним состоянием. Недетерминированные конечные автоматы

37 Запись δ(q, a) = {p 1, p 2,..., p k } означает, что недетерминированный конечный автомат M в состоянии q, сканируя символ a на входной ленте, продвигает входную головку вправо к следующей ячейке и выбирает любое из состояний p 1, p 2,..., p k в качестве следующего. Недетерминированные конечные автоматы

38 Недетерминированные конечные автоматы Область определения δ может быть расширена на Q Σ * следующим образом: δ(q, ) = {q}, для каждого x Σ * и a Σ. Область определения δ может быть расширена далее до 2 Q Σ * следующим образом: δ({p 1, p 2,..., p k }, x) =

39 Определение 3.7. Цепочка x Σ * принимается недетерминированным конеч- ным автоматом M, если существует состояние p, такое, что p F и p δ(q 0, x). Множество всех цепочек x, принимаемых ndfa M, обозначается T(M). Замечание 3.2. Напомним, что 2 Q, где Q любое множество, обозначает степенное множество или множество всех под- множеств множества Q. Недетерминированные конечные автоматы

40 Пример 3.2. Рассмотрим ndfa, который распознает множество {0,1} * {00,11}{0,1} * : M = ({q 0, q 1, q 2, q 3, q 4 }, {0, 1}, δ, q 0, {q 2, q 4 }), где δ(q 0, 0) = {q 0, q 3 }, δ(q 0, 1) = {q 0, q 1 }, δ(q 1, 0) =, δ(q 1, 1) = {q 2 }, δ(q 2, 0) = {q 2 }, δ(q 2, 1) = {q 2 }, δ(q 3, 0) = {q 4 }, δ(q 3, 1) =, δ(q 4, 0) = {q 4 }, δ(q 4, 1) = {q 4 }. Недетерминированные конечные автоматы

41 На рис. 3.3 приведена диаграмма переходов этого автомата. Фактически он принимает любые цепочки, составленные из нулей и единиц, в которых встречаются два подряд идущих нуля или единицы. Недетерминированные конечные автоматы

42 Рис Диаграмма переходов. Недетерминированные конечные автоматы q1q1 00 q3q3 q0q0 0,1 1 1 q2q2 q4q4 Start

43 Теорема 3.3. Пусть L язык, распоз- наваемый недетерминированным конечным автоматом. Тогда существует детерми- нированный конечный автомат, который распознаёт L. Доказательство. Пусть M = (Q, Σ, δ, q 0, F) ndfa и L = T (M). Определим dfa следующим образом. Ret 52 Ret 75

44 Эквивалентность недетерминированных и детерминированных конечных автоматов Положим Q = {[s] s 2 Q }. Состояние из множества Q будем представлять в виде [q 1, q 2,..., q i ], где q i Q (i > 0). Обозначение будем использовать в случае, когда i = 0, то есть s =. Начальное состояние q 0 = [q 0 ]. Таким образом, dfa будет хранить след всех состояний, в которых ndfa M мог бы быть в любой данный момент.

45 Пусть множество всех состояний из Q, содержащих хотя бы одно состояние из множества конечных состояний F. Входной алфавит Σ = Σ такой же, как в данном ndfa M. Эквивалентность недетерминированных и детерминированных конечных автоматов

46 Определим тогда и только тогда, когда Индукцией по длине l входной цепочки x Σ * легко показать, что тогда и только тогда, когда Эквивалентность недетерминированных и детерминированных конечных автоматов

47 База. Пусть l = 0. Утверждение выполняется, ибо δ(q 0, ) = q 0 = [q 0 ] и δ(q 0, ) = {q 0 }. Индукционная гипотеза. Предположим, что утверждение выполняется для всех l n (n 0). Индукционный переход. Докажем, что тогда утверждение выполняется и для l = n + 1. Эквивалентность недетерминированных и детерминированных конечных автоматов

48 Пусть x = za, где z Σ *, z = n, a Σ. Тогда δ(q 0, x) = δ(q 0, za) = δ (δ(q 0, z), a). По индукционному предположению δ(q 0, z) = [q 1, q 2,..., q i ] тогда и только тогда, когда δ(q 0, z) = {q 1, q 2,..., q i }. В то же время по построению δ([q 1, q 2,..., q i ], a) = [p 1, p 2,..., p j ] тогда и только тогда, когда δ({q 1, q 2,..., q i }, a) = {p 1, p 2,..., p j }. Эквивалентность недетерминированных и детерминированных конечных автоматов (1) (2)

49 Эквивалентность недетерминированных и детерминированных конечных автоматов Таким образом, учитывая (1) и (2), имеем δ(q 0, x) = δ(q 0, za) = = δ([q 1, q 2,..., q i ], a) = [p 1, p 2,..., p j ] тогда и только тогда, когда δ(q 0, x) = δ(q 0, za) = = δ({q 1, q 2,..., q i }, a) = {p 1, p 2,..., p j }.

50 Эквивалентность недетерминированных и детерминированных конечных автоматов Чтобы закончить доказательство, остается добавить, что точно тогда, когда δ(q 0, x) содержит состоя- ние из множества конечных состояний F. Следовательно, T(M) = T( ). Что и требовалось доказать.

51 Пример 3.3. Пусть M = ({q 0, q 1 }, {0, 1}, δ, q 0, {q 1 }) ndfa, где δ(q 0, 0) = {q 0, q 1 }, δ(q 0, 1) = {q 1 }, δ(q 1, 0) =, δ(q 1, 1) = {q 0, q 1 }. См. рис. 3.4 (а). Эквивалентность недетерминированных и детерминированных конечных автоматов 1 0,1 q0q0 q1q1 q0q0 0 q1q1 1 0 Рис. 3.4 (a). Недетерминированный автомат M. Start

52 Построим детерминированный конечный автомат, эквивалентный данному. Положим Согласно теореме 3.3 в качестве состояний детерминированного автомата следует взять все подмножества множества {q 0, q 1 }, включая пустое:3.3 Пример 3.3.

53 Q = {, [q 0 ], [q 1 ], [q 0, q 1 ]}, причём Конечные состояния автомата пред- ставлены теми подмножествами, которые содержат конечные состояния данного автомата (в нашем случае q 1 ), т. е. = {[q 1 ], [q 0, q 1 ]}. Пример 3.3.

54 Наконец, δ([q 0 ], 0) = [q 0, q 1 ], δ([q 0 ], 1) = [q 1 ], δ([q 1 ], 0) =, δ([q 1 ], 1) = [q 0, q 1 ], δ([q 0, q 1 ], 0) = [q 0, q 1 ], δ([q 0, q 1 ], 1) = [q 0, q 1 ], δ (, 0) =, δ(, 1) =. Пример 3.3. Поясним, что δ([q 0, q 1 ], 0) = [q 0, q 1 ], так как δ(q 0, 0) = {q 0, q 1 }, δ(q 1, 0) =, и {q 0, q 1 } = {q 0, q 1 }. Аналогично, δ([q 0, q 1 ], 1) = [q 0, q 1 ], ибо δ(q 0, 1) = {q 1 }, δ(q 1, 1) = {q 0, q 1 } и {q 1 } {q 0, q 1 } = {q 0, q 1 }. См. рис. 3.4 (б).рис. 3.4 (б)

55 Рис. 3.4 (б). Детерминированный автомат. 1 [q0][q0] [q1][q1] [q0,q1][q0,q1] 1 0 0,1 0 0,1 Пример 3.3. Состояние можно удалить как бесполезное (состояние ошибки), ибо из него не достижимо никакое конечное. Start

56 § 3.4. Конечные автоматы и языки типа 3 Теперь мы возвращаемся к связи языков, порождаемых грамматиками типа 3, с множествами, которые распознаются конечными автоматами. Для удобства рассуждений введём понятие конфигурации конечного автомата, которое относится как dfa, так и к ndfa.

Определение 3.8. Пусть M = (Q, Σ, δ, q 0, F) конечный автомат. Конфигурацией конечного автомата M назовём состояние управления q Q в паре с непрочитанной частью входной цепочки от текущего символа до конца входной цепочки x Σ * : (q, x). 57 Конечные автоматы и языки типа 3 a1a1 a2a2...aiai ai+1ai+1 anan q q0q0 q1q1 x Рис. 3.0 а

58 Конечные автоматы и языки типа 3 Пусть (q, ax) конфигурация fa M, где q Q, a Σ, x Σ *, и пусть p = δ(q, a) в случае, если M dfa, или p δ(q, a) в случае, когда M ndfa. Тогда fa M может перейти из конфигура- ции (q, ax) в конфигурацию (p, x), и этот факт мы будем записывать как (q, ax) (p, x).

59 Конечные автоматы и языки типа 3 Далее символом обозначается рефлексивно-транзитивное замыкание отношения непосредственного следования конфигураций на множестве конфигураций. Запись (q 0, x) (p, ), где p F, равнозначна записи x T(M).

60 Теорема 3.4. Пусть G = (V N, V T, P, S) грамматика типа 3. Тогда существует конечный автомат M = (Q, Σ, δ, q 0, F), такой, что T(M) = L(G). Доказательство. Построим ndfa M, о котором идёт речь. В качестве состояний возьмём нетерминалы грамматики и ещё одно дополнительное состояние A V N : Q = V N {A}, причём начальное состояние автомата M есть q 0 = S. Конечные автоматы и языки типа 3 Ret 74

61 Предполагается, что начальный нетер- минал S не будет появляться в правых частях правил, если S P (см. лемму 2.1). 2.1 Включим A в δ(B, a), если B a P. Кроме того, в δ(B, a) включим все C V N, такие, что B aС P. Положим δ(A, a) = для каждого a V T. L = L(G) L = T(M) {S, A}, если S P ; {A}, если S P. F =

62 Построенный автомат M, принимая цепочку x, моделирует её вывод в грамматике G. Требуется показать, что T(M) = L(G). L = L(G) L = T(M)

63 I. Пусть x = a 1 a 2...a n и x L(G), n 1. Тогда существует вывод вида S a 1 A 1 a 1 a 2 A 2... a 1 a 2... a n – 1 A n – 1 a 1 a 2...a n – 1 a n, где A 1,..., A n – 1 V N. Очевидно, что в нём используются следующие правила: S a 1 A 1, A 1 a 2 A 2,..., A n – 2 a n – 1 A n – 1, A n – 1 a n P. По построению δ имеем: A 1 δ(S, a 1 ), A 2 δ(A 1, a 2 ),..., A n – 1 δ(A n – 2, a n – 1 ), A δ(A n – 1, a n ). (q 0, x) (p, ) Если то

64 Следовательно, существует последователь- ность конфигураций (S, a 1 a 2...a n ) (A 1, a 2...a n ) … … (A n – 1, a n ) (A, ), причём A F и потому x T(M). Если же x =, то есть в данном выводе используется правило S P, и по по- строению автомата в этом случае S F, то (S, ) (S, ) (рефлексивность!), т. е. x T(M). (q 0, x) (p, ) Если то

65 Если (q 0, x) (p, ), то II. Пусть теперь x = a 1 a 2 …a n и x T(M), n 1. Тогда существует последовательность конфигураций вида (S, a 1 a 2...a n ) (A 1, a 2...a n ) (A n – 2, a n 1 ) (A n – 1, a n ) (A, ), где A F. Очевидно, что A 1 δ(S, a 1 ), A 2 δ(A 1, a 2 ),..., A n – 1 δ(A n – 2, a n – 1 ), A δ(A n – 1, a n ). Ret 79

66 Но это возможно лишь при условии, что существуют правила S a 1 A 1, A 1 a 2 A 2,..., A n – 2 a n – 1 A n – 1, A n – 1 a n P. Используя их, легко построить вывод вида S a 1 A 1 a 1 a 2 A 2... a 1 a 2... a n – 1 A n – 1 a 1 a 2... a n – 1 a n = x, т. е. x L(G). Если же x = и x T(M), то (S, ) (S, ) и S F. Но это возможно, если только суще- ствует правило S P. А тогда S и x L(G). Что и требовалось доказать. Если (q 0, x) (p, ), то

67 Теорема 3.5. Пусть M = (Q, Σ, δ, q 0, F) конечный автомат. Существует грамматика G типа 3, такая, что L(G) = T(M). Доказательство. Без потери общности можно считать, что M dfa. Построим грамматику G = (V N, V T, P, S), положив V N = Q, V T = Σ, S = q 0, P = {q ap δ(q, a) = p} {q a δ(q, a) = p и p F}. Очевидно, что G грамматика типа 3. Конечные автоматы и языки типа 3 Ret 79

68. Если x T(M), то x L(G) I.Пусть x T(M) и x > 0. Покажем, что x L(G). Предположим, что x = a 1 a 2 … a n, n > 0. Существует последовательность конфи- гураций автомата M (q 0, a 1 a 2...a n ) (q 1, a 2...a n )... (q n – 1, a n ) (q n, ), причём q n F. Соответственно δ(q 0, a 1 ) = q 1, δ(q 1, a 2 ) = q 2,..., δ(q n – 1, a n ) = q n.

69 По построению грамматики в множестве правил P существуют правила вида q i a i + 1 q i + 1 (i = 0, 1,..., n – 2) и правило q n – 1 a n. С их помощью можно построить вывод S = q 0 a 1 q 1 a 1 a 2 q 2... a 1 a 2 …a n – 1 q n – 1 a 1 a 2 … a n. А это значит, что x L(G). Если x T(M), то x L(G)

70 II. Пусть x L(G) и x > 0. Покажем, что x T(M). Предположим, что x = a 1 a 2 … a n, n > 0. Существует вывод вида q 0 a 1 q 1 a 1 a 2 q 2... a 1 a 2 …a n – 1 q n – 1 a 1 a 2 … a n – 1 a n. Соответственно существуют правила q i a i + 1 q i + 1 (i = 0, 1,..., n – 2) и правило q n – 1 a n. Если x L(G), то x T(M)

71 Если x L(G), то x T(M) Очевидно, что они обязаны своим существованием тому, что δ(q i, a i + 1 ) = q i + 1 (i = 0, 1,..., n – 2) и q n F. А тогда существует последовательность конфигураций fa M вида (q 0, a 1 a 2 … a n ) (q 1, a 2... a n ) …... (q n – 2, a n 1 ) (q n – 1, a n ) (q n, ), причём q n F. Это значит, что x T(M).

72 Если q 0 F, то T(M) и L(G) = T(M). Если q 0 F, то T(M). В этом случае L(G) = T(M) \ { }. По теореме 2.2 мы можем получить из G новую грамматику G 1 типа 3, такую, что2.2 L(G 1 ) = L(G) { } = T(M). Что и требовалось доказать. Если x L(G), то x T(M)

73 Пример 3.4. Рассмотрим грамматику типа 3 G = ({S, B}, {0, 1}, P, S), где P = {S 0B, B 0B, B 1S, B 0}. Мы можем построить ndfa M = ({S, B, A}, {0, 1}, δ, S, {A}), где δ определяется следующим образом: 1) δ(S, 0) = {B},2) δ(S, 1) =, 3) δ(B, 0) = {B, A},4) δ(B, 1) = {S}, 5) δ(A, 0) =,6) δ(A, 1) =. Конечные автоматы и языки типа 3 Ret 81Ret 80

74 По теореме 3.5 T(M) = L(G), в чём легко убедиться и непосред- ственно, ибо:теореме 3.5 (1) S = 0B; (2) B = 0B 0 1S; Подставим (1) в (2), получаем: (2 ) B = 0B 0 10B = 0 (0 10) B = (0 10) * 0. Подставим (2 ) в (1), получаем: (1 ) S = 0(0 10) * 0, т. е. L = L(G) = 0(0 10) * S BA Пример 3.4 Рис. 3.5 (а). ndfa M. 0, 1 0, 1

75 Пример 3.4 Теперь мы используем построения теоремы 3.4, чтобы найти dfa, эквивалентный ndfa M. 3.4 Положим = (, {0, 1},, [S], ), где = {, [S], [B], [A], [S, B], [S, A], [B, A], [S, B, A]}, = {[A], [S, A], [B, A], [S, B, A]};

76 Пример 3.4 Отображение определяется следующим образом: 1) ([S], 0) = [B],2) ([S], 1) =, 3) ([B], 0) = [B, A], 4) ([B],1) = [S], 5) ([B, A], 0) = [B, A], 6) ([B, A],1) = [S], 7) (, 0) =,8) (, 1) =. Ret 78 Намним, что в ndfa M: 1) δ(S, 0) = {B},2) δ(S, 1) =, 3) δ(B, 0) = {B, A},4) δ(B, 1) = {S}, 5) δ(A, 0) =,6) δ(A, 1) =.

[S][S] [B][B] [BA] Рис. 3.5 (б). dfa. Пример 3.4 Start

Ни в какие другие состояния, кроме, [S], [B], [B, A], автомат никогда не входит, и они могут быть удалены из множеств состояний, как бесполезные. Кроме того, ясно, что из состояния нет пути к единственному конечному состоянию [B, A], т. е. состояние ошибки. Его можно было бы отбросить со всеми инцидентными дугами. Обозначим полученный таким образом dfa и (8). 78 Пример 3.4 где и отличается от отсутствием равенств (2), (7)равенств

[S][S] [B][B] [BA] P = {(1) [S] 0[B], (2) [B] 0[B, A], (3) [B] 0, (4) [B] 1[S], (5) [B, A] 0[B, A], (6) [B, A] 0, (7) [B, A] 1[S]. Теперь согласно пост- роениям теоремы 3.5 по автомату построимтеоремы 3.5 грамматику типа 3: G 1 = (V N, V T, P, S), где V N = {[S], [B], [B, A]}, V T = {0, 1}, S = [S], Пример 3.4 Рис. 3.5 (в). dfa.

80 Грамматика G 1 сложнее грамматики G, но согласно трём предыдущим теоремам L(G 1 ) = L(G).G Однако, грамматику G 1 можно упростить, если заметить, что правила для [B, A] порождают в точности те же цепочки, что и правила для [B]. И в самом деле, правило (2) приписывает 0 к цепочкам, порождаемым нетерминалом [B, A], но правило (5) даёт сколько угодно 0 в начале этих цепочек и без этого правила (2). Поэтому нетерминал [B, A] можно заменить всюду на [B] и исключить появившиеся дубликаты правил для [B]. Пример 3.4

81 В результате получим грамматику G 2 = ({[S], [B]}, {0, 1}, P 2, [S]), где P 2 = {(1) [S] 0[B], (2) [B] 0[B], (3) [B] 0, (4) [B] 1[S]}. Очевидно, что полученная грамматика G 2 отличается от исходной грамматики G лишь обозначениями нетерминалов.G Другими словами, L(G 2 ) = L(G). Пример 3.4

82 § 3.5. Свойства языков типа 3 Поскольку класс языков, порождаемых грамматиками типа 3, равен классу множеств, распознаваемых конечными автоматами, мы будем использовать обе формулировки при описании свойств класса языков типа 3. Прежде всего покажем, что языки типа 3 образуют булеву алгебру.

83 Свойства языков типа 3 Определение 3.9. Булева алгебра множеств есть совокупность множеств, замкнутая относительно операций объединения, дополнения и пересечения. Определение Пусть L 1 * некоторый язык и 1 2. Под дополнением языка L подразуме- вается множество Пояснение. Вложение 1 2 предполагает, что дополнению принадлежат не только цепочки из законных символов из 1, но и цепочки, содержащие незаконные символы, т. е. символы не из 1.

84 Лемма 3.1. Класс языков типа 3 замкнут относительно объединения. Доказательство. Возможны два подхода: один использует недетерминированные конечные автоматы, другой основывается на грамматиках. Мы будем пользоваться вторым подходом. Свойства языков типа 3 Ret 92 Ret 112

85 Замкнутость rs относительно объединения Пусть L 1 = L(G 1 ) и L 2 = L(G 2 ), где G 1 = (,, P 1, S 1 ) и G 2 = (,, P 2, S 2 ). граматики типа 3. Можно предположить, что ибо в противном случае этого всегда можно достичь путём переименования нетермина- лов данных грамматик. Предположим также, что

86 Построим новую грамматику G 3 = (,, P 3, S), где P 3 = (P 1 P 2 )\{S 1, S 2 } {S S 1 P 1 или S 2 P 2 }. Очевидно, что тогда и только тогда, когда или В первом случае из могут выводиться только цепочки в алфавите во втором в алфавите Замкнутость rs относительно объединения

87 Замкнутость rs относительно объединения Аналогично, если то тогда и только тогда, когда Формально, если, то тогда и только тогда, когда

88 Сопоставив всё сказанное, заключаем, что тогда и только тогда, когда либо либо. А это и значит, что L(G 3 ) = L(G 1 ) L(G 2 ). Что и требовалось доказать. Замкнутость rs относительно объединения

89 Замкнутость rs относительно дополнения Лемма 3.2. Класс множеств, распознаемых конечными автоматами (порождаемых грамматиками типа 3), замкнут относительно дополнения. Доказательство. Пусть M = (Q, 1,, q 0, F) dfa и T(M) = L. Пусть 2 конечный алфавит, содержа- щий 1, т. е Мы построим fa M, который распознаёт Ret 92 Ret 97

90 Замкнутость rs относительно дополнения Положим M = (Q, 2,,, F ), где Q = Q {d}, F = (Q \ F ) {d}, где d Q новое состояние ловушка. (1)(q, a) = (q, a) для каждого q Q и a 1, если (q, a) определено; (2)(q, a) = d для тех q Q и a 2, для которых (q, a) не определено; (3)(d, a) = d для каждого a 2. Ret 97

91 Замкнутость rs относительно дополнения Интуитивно fa M получается расширением входного алфавита 1 fa M до алфавита 2, добавлением состояния ловушки d и затем перестановкой конечных и неконечных состояний. Очевидно, что fa M распознаёт язык

92 Теорема 3.6. Класс множеств, принимаемых конечными автоматами, образует булеву алгебру. Доказательство непосредственно следует из лемм 3.1 и 3.2 и того факта, что Ret 137

93 Теорема 3.7. Все конечные множества распознаются конечными автоматами. Доказательство. Рассмотрим множество, содер- жащее только одну цепочку x = a 1 a 2 …a n, n > 0. Мы можем построить конечный автомат M, принимающий только эту цепочку. Положим M = ({q 0, q 1, q 2,…, q n, p}, {a 1, a 2,..., a n }, δ, q 0, {q n }), где 1. δ(q i, a i + 1 ) = q i + 1, 2. δ(q i, a) = p, если a a i + 1 (i = 0, 1,..., n – 1), 3. δ(q n, a) = δ(p, a) = p для всех a. Очевидно, что fa M принимает только цепочку x. Регулярность конечных множеств Ret 112

94 Множество, содержащее только пустую цепочку, распознаётся конечным автоматом M = ({q 0, p},, δ, q 0, {q 0 }), где δ(q 0, a) = δ(p, a) = p для всех a. Действительно, только пустая цепочка оставит автомат в состоянии q 0, являющееся конечным. Пустое множество распознаётся конечным автоматом M = ({q 0 },, δ, q 0, ), где δ(q 0, a) = q 0 для всех a. Утверждение теоремы немедленно следует из свойства замкнутости языков типа 3 относи- тельно объединения. Что и требовалось доказать. Регулярность конечных множеств

95 Определение Произведением или конкатенацией языков L 1 и L 2 называется множество L 1 L 2 = {z z = xy, x L 1, y L 2 }. Другими словами, каждая цепочка в языке L 1 L 2 есть конкатенация цепочки из L 1 с цепочкой из L 2. Например, если L 1 = {01, 11} и L 2 = {0, 1, 101}, то множество L 1 L 2 = {010, 011, 01101, 110, 111, 11101}. Свойства языков типа 3

96 Теорема 3.8. Класс множеств, распознаваемых конечными автоматами, замкнут относительно произведения. Доказательство. Пусть M 1 = (Q 1, Σ 1, δ 1, q 1, F 1 ) и M 2 = (Q 2, Σ 2, δ 2, q 2, F 2 ) детерминированные конечные автоматы, распознающие языки L 1 и L 2 соответственно. Замкнутость rs относительно конкатенации Ret 112

97 Без потери общности можно предполагать, что (1) Q 1 Q 2 = и (2) Σ 1 = Σ 2 = Σ, ибо противном случае мы могли бы доба- вить в Q 1 и Q 2 мёртвые состояния, вроде состояния ловушки d, как при доказатель- стве леммы Замкнутость rs относительно конкатенации

98 Именно, сохраняя прежние обозначения для fa M 1 и M 2, положим M 1 = (Q 1 {d 1 }, Σ, δ 1, q 1, F 1 ), M 2 = (Q 2 {d 2 }, Σ, δ 2, q 2, F 2 ), где Σ = Σ 1 Σ 2, а исходные отображения δ 1 и δ 2 пополним равенствами: 1 (q, a) = d 1 для каждого q Q 1 и a Σ 2 \ Σ 1, 1 (d 1, c) = d 1 для каждого c Σ, 2 (p, b) = d 2 для каждого p Q 2 и b Σ 1 \ Σ 2, 2 (d 2, c) = d 2 для каждого c Σ. Замкнутость rs относительно конкатенации

99 Мы построим ndfa M, распознающий язык L 1 L 2. Положим M = (Q 1 Q 2, Σ, δ, q 1, F), где 1) δ(q, a) = {δ 1 (q, a)} для любого q Q 1 \ F 1, 2) δ(q, a) = {δ 1 (q, a), δ 2 (q 2, a)} для любого q F 1, 3) δ(q, a) = {δ 2 (q, a)} для любого q Q 2. Если L 2, то F = F 2, иначе F = F 1 F 2. Замкнутость rs относительно конкатенации

100 Правило 1 воспроизводит движения авто- мата M 1 до тех пор, пока он не достигает какого-нибудь из его конечных состояний, приняв некоторую (возможно пустую) начальную часть входной цепочки, принад- лежащей языку L 1. Затем согласно правилу 2 он может продолжать повторять движения автомата M 1 или перейти в режим воспроизведения движений автомата M 2, начиная с его начального состояния (на том же текущем входном символе). Замкнутость rs относительно конкатенации

101 В последнем случае все дальнейшие движения, благодаря правилу 3, повторяют движения автомата M 2. Если fa M 2 принимает (возможно пустое) окончание входной цепочки, принадлежащее языку L 2, то и автомат M принимает всю входную цепочку. Другими словами, T(M) = L 1 L 2. Замкнутость rs относительно конкатенации

102 Замкнутость rs относительно замыкания Определение Замыкание языка L есть множество Предполагается, что L 0 = { }, L n = L n – 1 L = LL n – 1 при n > 0. Пример 3.5. Если L = {01, 11}, то L * = {, 01, 11, 0101, 0111, 1101, 1111,...}.

103 Теорема 3.9. Класс множеств, принимаемых конечными автоматами, замкнут относительно замыкания. Доказательство. Пусть M = (Q, Σ, δ, q 0, F) dfa и L = T(M). Построим ndfa M, который распознаёт язык L *. Положим M = (Q {q 0}, Σ, δ, q 0, F {q 0}), где q 0 Q новое состояние; Замкнутость rs относительно замыкания Ret 112

104 Замкнутость rs относительно замыкания для всех a : δ (q 0, a) = {δ(q 0, a), q 0 }, если δ(q 0, a) F, {δ(q 0, a)} в противном случае; δ (q, a) = {δ(q, a), q 0 }, если δ(q, a) F, {δ(q, a)} в противном случае. Предназначение нового начального состояния принимать пустую цепочку. Если q 0 F, мы не можем просто сделать q 0 конечным состоянием, поскольку автомат M может снова прийти в состояние q 0, прочитав некоторую непустую цепочку, не принадлежащую языку L. для всех q Q и a :

105 Докажем теперь, что T(M ) = L *. I. Предположим, что x L *. Тогда либо x =, либо x = x 1 x 2...x n, где x i L (i = 1, 2,..., n). Очевидно, что автомат M принимает. Ясно также, что из x i L следует, что δ(q 0, x i ) F и множества δ(q 0, x i ) и δ(q 0, x i ) каждое содержит состояние q 0 и некоторое состояние p F (возможно p = q 0 ). Замкнутость rs относительно замыкания

106 Замкнутость rs относительно замыкания Итак, (q 0, x) = (q 0, x 1 x 2 … x n ) (q 0, x 2 … x n ) … … (q 0, x n ) (p, ), где p F. Следовательно, x T(M ).

107 Замкнутость rs относительно замыкания II. Предположим теперь, что x = a 1 a 2...a n T(M ): (q 0, a 1 a 2...a n ) (q 1, a 2...a n ) … (q n 1, a n ) (q n, ), q i Q (i = 1, 2, …, n), причём q n F {q 0 }. Ясно, что q n = q 0 только в случае n = 0. В общем случае существует подпоследо- вательность состояний такая, что значение

108 Замкнутость rs относительно замыкания x = a 1 a 2... a j 1 a j 1 +1 … a j 2 a j 2 +1 … a j m +1 … a n x1x1 x2x2 xmxm q 0 q0q0 q0q0 q0q0 T(M ) q i m = q n F L L L x = x 1 x 2... x m L m L *.

109 Замкнутость rs относительно замыкания Это значит, что в такие моменты ndfa M заканчивает просмотр очередного фрагмен- та x, принимаемого dfa M. Формально, при некоторых j = j k (1 k m) имеет место Поэтому x = x 1 x 2... x m, где δ(q 0, x k ) F для 1 k m. Это означает, что x k L, а x L m L *. Что и требовалось доказать. δ, но не δ !

Теорема (С.Клини). Класс множеств, принимаемых конечными автоматами, является наименьшим классом, содержа- щим все конечные множества, замкнутым относительно объединения, произведения и замыкания.С.Клини Доказательство. Обозначим класс регу- лярных множеств буквой M, а наименьший класс множеств, принимаемых конечными автоматами, содержащий все конечные множества и замкнутый относительно объединения, произведения и замыкания, буквой. 110

Stephen Cole Kleene 111 January 5, 1909, Hartford, Connecticut, United States – January 25, 1994, Madison, Wisconsin

112 Теорема (С.Клини). То, что M, является непосредственным следствием из леммы 3.1 (объединение) и теорем 3.7 (конечные множества), 3.8 (произведение) и 3.9 (замыкание) Остается показать обратное вложение, то есть, что M.

113 Теорема (С.Клини). Пусть L 1 множество, принимаемое некоторым dfa M = ({q 1, q 2,..., q n }, Σ, δ, q 1, F). Требуется показать, что L 1 = T(M). Пусть обозначает множество всех цепочек x, таких, что δ(q i, x) = q j, причём, если y является непустым префиксом x, не совпадающим с x (x = yz, y, z ), то δ(q i, y) = q l, где l k.

114 Теорема (С.Клини). Другими словами, множество всех цепочек, которые переводят fa M из состо- яния q i в состояние q j, не проходя через какое-либо состояние q l, где l > k. Под прохождением через состояние q l мы подразумеваем вход в состояние q l и выход из него. Но i и j могут быть больше k. Мы можем определить рекурсивно:

115 Приведённое определение неформально означает, что цепочки, которые переводят автомат M из состояния q i в состояние q j без перехода через состояния выше, чем q k, (1) либо все находятся во множестве, т. е. никогда не приводят автомат в состоя- ние столь высокое, как q k, Теорема (С.Клини).

116 (2) либо каждая такая цепочка начинается с цепочки из множества (которая пере- водит автомат M в состояние q k первый раз), за которой следует сколько-то цепочек из множества, переводящих автомат M из состояния q k снова в состояние q k без перехода через состояние q k и высшие по номеру состояния, за которыми следует цепочка из множества, переводящая автомат M из состояния q k в состояние q j, не достигая состояния q k и большие по номеру состояния. Теорема (С.Клини).

117 Теорема (С.Клини). Индукцией по параметру k мы можем показать, что множество для всех i и j находятся в пределах класса. База. Пусть k = 0. Утверждение очевидно, поскольку все множества являются конечными. Индукционная гипотеза. Предположим, что утверждение выполняется для всех k, таких, что 0 k m (0 m < n).

118 Теорема (С.Клини). Индукционный переход. Докажем, что утверждение верно и для k = m + 1. Это так, поскольку выражается через объединение, конкатенацию и замыкание различных множеств вида, каждое из которых по индукционному предположе- нию находится в классе. Остается заметить, что Итак, из L 1 = T(M) следует, что L 1. Что и требовалось доказать.

119 Следствие 3.1 (из теоремы Клини). Из теоремы 3.10 следует, что любое выраже- ние, построенное из конечных подмно- жеств множества *, где конечный алфавит, и конечного числа операций объединения, произведения. (символ обычно опускаемый) и замыкания * со скобками, которые определяют порядок действий, обозначает множество, прини- маемое некоторым конечным автоматом. Теорема (С.Клини).

120 И наоборот, каждое множество, принимаемое некоторым конечным автоматом, может быть представлено в виде такого выражения, которое называется регулярным выражением. Теорема (С.Клини).

121 Регулярные выражения Пример 3.5: числа языка Паскаль. Пусть D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Тогда любое число языка Паскаль можно представить в виде следующего регулярного выражения: D + ({.}D + { }) ({e}({+, –} { }) D + { }). Здесь использован символ плюс Клини (+), определяемый следующими равенствами: A + = A * A = A A * =

122 Напомним, что звездочка Клини (*), обозначающая замыкание, определяется следующим равенством: A * = В примере 3.5 члены { } обеспечивают необязательность дробной части, знака порядка и самого порядка.3.5 Минимальная цепочка, представляющая число на языке Паскаль, состоит из одной цифры. Регулярные выражения

123 Регулярные выражения Если ввести обозначение [R] = R { }, где R регулярное выражение, то множество чисел языка Паскаль можно представить следующей регулярной формулой: D + [.D + ] [ e[+, –]D + ].

124 § 3.6. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов В этом параграфе мы покажем, что существуют алгоритмы, отвечающие на многие вопросы, касающиеся конечных автоматов и языков типа 3.

125 Теорема Множество цепочек, принимаемых конечным автоматом с n состояниями, 1) не пусто, тогда и только тогда, когда он принимает цепочку, длина которой меньше n; 2) бесконечно, тогда и только тогда, когда он принимает цепочку, длина l которой удовлетворяет неравенству: n l < 2n. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов Ret 137

126 Доказательство. Необходимость условия 1 вытекает из следующих рассуждений от противного. Предположим, что множество T(M), но ни одной цепочки длиной меньше n в этом множестве не существует. Пусть x T(M), где M = (Q, Σ, δ, q 0, F) конечный автомат с n состояниями, и x n, и пусть x одна из самых коротких таких цепочек. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов

127 Очевидно, что существует такое состояние q Q, что x = x 1 x 2 x 3, где x 2, и δ(q 0, x 1 ) = q, δ(q, x 2 ) = q, δ(q, x 3 ) F. Но тогда x 1 x 3 T(M), поскольку δ(q 0, x 1 x 3 ) = δ(q 0, x 1 x 2 x 3 ) F. В то же время x 1 x 3 < x 1 x 2 x 3 = x, но это противоречит предположению, что x одна из самых коротких цепочек, принимаемых fa M. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов

128 Достаточность условия 1 очевидна. Действительно, если конечный автомат принимает цепочку с меньшей длиной, чем n, то множество T(M) уже не пусто (какой бы длины цепочка ни была). Алгоритмически разрешимые проблемы, касающиеся конечных автоматов

129 Докажем теперь утверждение 2. Необходимость условия 2 доказывается способом от противного. Пусть fa M принимает бесконечное множество цепочек, и ни одна из них не имеет длину l, n l < 2n. Если бы в множестве T(M) существовали только цепочки длиной l < n, то язык был бы конечен, но это не так. Поэтому существуют и цепочки длиной l 2n. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов

130 Пусть x одна из самых коротких цепочек, таких, что x T(M) и x 2n. Очевидно, что существует такое состояние q Q, что x = x 1 x 2 x 3, где 1 x 2 n, и δ(q 0, x 1 ) = q, δ(q, x 2 ) = q, δ(q, x 3 ) F. Но тогда x 1 x 3 T(M), поскольку δ(q 0, x 1 x 3 ) = δ(q 0, x 1 x 2 x 3 ) F при том, что x 1 x 3 n, ибо x = x 1 x 2 x 3 2n и 1 x 2 n. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов

131 Поскольку по предположению в T(M) цепочек длиной n l < 2n не существует, то x 1 x 3 2n. Следовательно, вопреки предположению, что x = x 1 x 2 x 3 T(M) одна из самых коротких цепочек, длина которой больше или равна 2n, нашлась более короткая цепочка x 1 x 3 T(M) и тоже с длиной, большей или равной 2n. Это противоречие доказывает необходимость условия 2. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов

132 Достаточность условия 2 вытекает из следующих рассуждений. Пусть существует x T(M), причём n x < 2n. Как и ранее, можем утверждать, что существует q Q, x = x 1 x 2 x 3, где x 2, и δ(q 0, x 1 ) = q, δ(q, x 2 ) = q, δ(q, x 3 ) F. Но тогда цепочки вида x 1 x 2 i x 3 T(M) при любом i 0. Очевидно, что множество T(M) бесконечно. Что и требовалось доказать. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов

133 Следствие 3.2. Из доказанной теоремы следует существование алгоритмов, разре- шающих вопрос о пустоте, конечности и бесконечности языка, принимаемого любым данным конечным автоматом. Действительно, алгоритм, проверяющий непустоту языка, может систематически генерировать все цепочки постепенно увеличивающейся длины, но меньшей n. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов

134 Каждая из этих цепочек пропускается через автомат. Либо автомат примет какую- нибудь из этих цепочек, и тогда алгоритм завершится с положительным ответом, либо ни одна из этих цепочек не будет принята, и тогда алгоритм завершится с отрицатель- ным результатом. В любом случае процесс завершается за конечное время. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов

135 Алгоритмически разрешимые проблемы, касающиеся конечных автоматов Алгоритм для проверки бесконечности языка можно построить аналогичным образом, только он должен генерировать и тестировать цепочки длины от n до 2n – 1 включительно.

136 Теорема Существует алгоритм для определения, являются ли два конечных автомата эквивалентными (т. е. распоз- нающими один и тот же язык). Доказательство. Пусть M 1 и M 2 конечные автоматы, распознающими языки L 1 и L 2 соответственно. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов

137 По теореме 3.6 множество3.6 распознаётся некоторым конечным автома- том M 3. Легко видеть, что множество L = T(M 3 ) не пусто тогда и только тогда, когда L 1 L 2. Следовательно, согласно теореме 3.12 существует алгоритм для определения, имеет ли место L 1 = L Что и требовалось доказать. Алгоритмически разрешимые проблемы, касающиеся конечных автоматов

138 Алгоритмически разрешимые проблемы, касающиеся конечных автоматов Пояснение. Необходимость утверждения L = L 1 = L 2 можно доказать следующим образом от противного. Пусть L=, но L 1 L 2. Это значит, например, что существует цепочка x L 1, такая что x L 2, т. е. x. Следовательно, x L 1. Но тогда L 1 и L, что противоречить предположению (L = ). Достаточность очевидна, ибо при L 1 = L 2 имеем Next