Главная Промышленная автоматика. w = Wi ... w, где для некоторой последовательности чисел ii. • im выполнены условия WrnoLjo л Д 1 <fe<m и /i -г. Так как g-решение, то g{X) = ay, \jcx,j,g{X,) и ... Uay„(X„) для всех / В частности, aag{Xj) и (jkg {Xk) g (Х) для всех / и Тогда wg(XjJ, w-imgii.,) и т. д. В конечном счете получаем, что цепочка tejtejtej .. - te принадлежит множеству g{Xj) =g{X;). Пришли к противоречию, так как предположили, что W не принадлежит g(X,). Таким образом, заключаем, что f(Xt)g(X) для всех 1. Отсюда непосредственно следует, что / - наименьшая неподвижная точка системы Q. □ Лемма 2,4. Пусть и Q-системы уравнений до и после одного применения шага 2 алгоритма 2.1. Тогда и имеют одну и ту же наименьшую неподвижную точку. Доказательство. Допустим, что на шаге 2 рассматривается уравнение (Заметим, что для 1</г<г коэффициент при А, равен 0.) В системах и Q. уравнения для А при hi совпадают. Допустим, что (2.2.14) - уравнение для Лу в системе при / > /. В системе уравнением для Лу будет (2.2.15) Ро = сс/о + сс а?«/о Pft o/ft + ay/aja4 для I <kn С помощью леммы 2.3 можно получить представления для наименьших неподвижных точек систем и Q, которые мы обозначим соответственно через и f. Из уравнения (2.2.15) видно, что каждая цепочка, принадлежащая /2(Лу), принадлежит (Лу). Это вытекает нз того, что любую цепочку waciai можно представить в виде W{dD. ... w„„ где waji, € а,- и w, ..., &у„ 1 ct;/. Таким образом, цепочка 5У является конкатенацией последовательности цепочек, каждая из которых принад- 2.2.2. Регулярные множества и праволинейные грамматики Покажем, что язык определяется праволинейной грамматикой тогда и только тогда, когда он является регулярным множеством. Чтобы доказать, что для каждого регулярного множества существует праволинейная грамматика, начнем с некоторых наблюдений. Пусть 2 - конечный алфавит. Лемма 2.6. Множества {1)0, (ii) {е} м (iii) {а} для всех а 2 являются праволинейными языками. Доказательство, (i) G({5}, 2, 0, 5) -праволинейная грамматика, для которой L{G) - 0 лежит множеству, обозначаемому некоторым коэффициентом системы Qi, и индексы этих коэффициентов удовлетворяют условию леммы 2.3. Аналогично для цепочек, принадлежащих ссуаа/. Так можно показать, что (Лу) (Лу). Чтобы доказать обратное включение, предположим, что wf(Aj). Тогда по лемме 2.3 w - w. ... Wj, где для некоторой последовательности ненулевых индексов Z, 1 выполнены условия гющо и pipip- для \р<т и = Можно однозначно сгруппировать цепочки Wp так, чтобы было wy.. .у,., где yp=-w • и (1) если ItL, то s = t-{- 1, (2) если lt> i, то s выбирается так, чтобы все 1 были равны i и lii. Отсюда следует, что в любом случае Ур-коэффициент при Л/ в уравнении для Ai системы Q, и, значит, wf(Aj). В итоге получаем, что ft(Aj) = f(Aj) для всех /. □ Лемма 2,5. Пусть Qj и -системы уравнений до и после одного применения шага 5 алгоритма 2.1. Тогда и Q. имеют одну и ту же наименьшую неподвижную точку. Доказательство. Доказательство аналогично доказательству леммы 2.4 и остается в качестве упражнения. □ Теорема 2.1. Алгоритм 2.1 находит наименьшую неподвижную точку стандартной системы уравнений. Доказательство. После того как шаг 5 применен для всех i, все уравнения принимают вид X/ = a, где а--регулярное выражение в алфавите 2. Ясно, что отображение /, для которого 1(Х)=ос, и будет наименьшей неподвижной точкой этой системы. □ е}, S) - праволинейная грамматика, для (ii) G = ({S} 2 {S. которой L (G) ~ {e}. (iii) Сд -({5}, 2, 5) -праволинейная грамматика, для которой L(Go) = {fl}. □ Лемма 2.7. Если и - праволинейные языки, то языки (\) LiUi-a, (ii) LL и (iii) LI тоже праволинейные. Доказательство. Так как языки Li и праволинейные, можно считать, что существуют праволинейные грамматики G,-(N„ 2, Л. и G,-(N,.2,/>3, 5,), для которых L (Gj и L((j = L. Будем также предполагать, что алфавиты Nj и Nj не пересекаются. Так как нетерминалы грамматики можно как угодно переименовывать, это предположение не приведет к потере общности. (i) Пусть Ga - праволинейная грамматика (N,UN,U{5J, 2, Л и Р. и {5,--5,15,}, 5) где 5з-новый нетерминальный символ, не принадлежащий hhNj, ии Ng. Ясно, 4ToL (Gg) = L(Gi) U L (G), так как для каждого вывода Sgw существует либо вывод Sj;>g,w, либо вывод 52=Фйг, и обратно. Так как - праволинейная грамматика, то L (Gg) - праволипейный язык. (ii) Пусть Gj- праволинейная грамматика (NjUN, 2, Р, 5), в которой определяется так: (1) Если А- хВ принадлежит Pj, то А-хВ принадлежит Р4. (2) Если А-л; принадлежит Р, то A-xS принадлежит Р4. (3) Все правила из Р принадлежат Р. Заметим, что если w, то 5, =>j wS, а если S=tx, то 5a=>J X. Таким образом, L (GJ L (G)L (GJ. Предположим теперь, что S->iw. Так как в Р пет правил вида А-х, которые попали туда из Р, то этот вывод можно записать в виде S-gxSgxy, где wxy и все правила, используемые в выводе ScuXS, попали в Р с помощью шагов (1) и (2). Следовательно, должны быть выводы 5i=j,a:h Sqy. Отсюда L(GJsL(G,)L(G2). Итак, L(G)=L(G,)L(G). (iii) Пусть грамматика Gj (N U {S}, 2, Pg, S) такова, что 5-не пр1£надлежит N, а Р5 строится следующим образом: (1) Если А-*хВ принадлежит Р, то А-хВ принадлежит Р5. (2) Если А-принадлежит Р, то A-xS и Л-х принадлежат Pg. (3) принадлежат Pg. Доказательство того, что Sq xS gxxSq ... .>G,i2 • • • п-\ь >G,i2 • • >n-xn тогда н только тогда, когда 5i=>jXi, 5, =»j, ла, ..., оставляем в качестве упражнения. Отсюда заключаем, что L (G5) (L (GJ) *. □ Теперь можно доказать, что класс праволинейных языков совпадает с классом регулярных множеств. Теорема 2.2. Язык является регулярным множеством тогда и только тогда, когда он праволипейный. Доказательство. Необходимость. Эта часть доказательства получается из лемм 2.6 и 2.7, если воспользоваться индукцией по числу шагов построения регулярного множества, где один шаг-это применение одного из правил, определяющих регулярные множества. Достаточность. Пусть G(N, 2, Р, S) - праволинейная грамматика и N = {4, Л,,}. Можно построить стандартную систему уравнений с регулярными коэф(})нциентами, неизвестными которой служат нетерминалы из N. Уравнение для Л- имеет вид л,- + • • • +о:,-„Л„, где (1) = Wf., если A->-w.j \ ... {Wf-все правила с левой частью Л и правой частью, состоящей только из терминалов (если - 0, полагаем -0); (2) для / > О cc(j =х+ ... +х, если Л;->хАу ... хАу - все правила с левой частью Л,- и правой частью, оканчивающейся на Л. (как и раньше, если т~0, то а,у = 0). С помощью леммы 2.3 можно показать, что L(G) = f{S), где f - наименьшая неподвижная точка построенной системы уравнений (это предлагаем в качестве упражнения). Но алгоритм 2.1 строит f (5) как язык, обозначаемый некоторым регулярным выражением. Таким образом, L (G) - регулярное множество. □ Пример 2.10. Пусть грамматика G определяется правилами ОЛ I 151е S А В -0S1Л -05 I \В Тогда соответствующая система уравнений получается из системы примера 2.9, если Х, Х, заменить соответственно на 5, Л, В. L(G) - это множество цепочек, в которых число нулей делится на 3. Нетрудно показать, что это множество обозначается регулярным выражением (2.2,13). □ 2,2.3. Конечные автоматы Мы рассмотрели три способа определения класса регулярных множеств: (1) класс регулярных множеств - наименьший класс языков, содержащий множества 0, {е\ и {а( для всех символов а н замкнутый относительно операций объединения, конкатенации и итерации; (2) регулярные множества - множества, определяемые регулярными выражениями; (3) регулярные множества - языки, порождаемые праволинейными грамматиками. Теперь опишем четвертый способ их определения с помощью конечных автоматов. Конечный автомат является одним из простейших распознавателей. „Бесконечной" памяти у него нет. Обычно конечный автомат состоит только из входной ленты и управляющего устройства с конечной памятью. Здесь мы позволим управляющему устройству быть недетерминированным, но входная головка будет односторонней. Фактически мы потребуем, чтобы входная головка сдвигалась вправо на каждом такте ). Двусторонний конечный автомат рассматривается в упражнениях. Мы определим конечный автомат, задав конечное множество его управляющих состояний, допустимые входные символы, начальное состояние и множество заключительных состояний, т. е. состояний, указывающих, что входная цепочка допускается. Задается также функция переходов состояний, которая по данному „текущему" состоянию и „текущему" входному символу указывает все возможные следующие состояния. Подчеркнем, что это устройство -недетерминированное в теоретико-автоматном смысле, т. е. оно переходит во все свои следующие состояния, если угодно, дублируя себя так, что в каждом из возможных следующих состояний находится один экземпляр этого устройства. Недетерминированный автомат допускает входную цепочку, если какой-нибудь из его параллельно работающих экземпляров достигает допускающего состояния. Недетермиинзм конечного автомата не следует смешивать со „случайностью*, при которой автомат может случайно выбрать одно из следующих состояний с фиксированными вероятностями, но этот автомат всегда имеется только в одном экземпляре. ) Напомним, что по определению односторонний распознаватель не сдвигает свою входную головку влево; ома, однако, может оставаться неподвижной .в течение такта. Если позволить конечному автомату оставлять свою входную головку неподвижной, это не даст ему возможности распознать язык, не распознаваемый обычным конечным автоматом. Такой автомат называется „вероятностным" и здесь изучаться не будет. Дадим формальное определение недетерминированного конечного автомага. Определение. Недетерминированный конечный автомат - это пятерка M = {Q, 2, б, i/, F), где (1) Q-конечное множество состояний; (2) 2 - конечное множество допустимых входных символов; (3) б - отображение множества Qx S в множество 5 (Q), определяющее поведение управляющего устройства; функцию б иногда называют функцией переходов; (4) (?о Q-начальное состояние управляющего устройства; (5) FQ - множество заключительных состояний. Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит ИЗ изменения состояния и сдвига входной головки на одну ячейку вправо. Для того чтобы определить будущее поведение конечного автомата, нужно знать лишь (1) текущее состояние управляющего устройства и (2) цепочку символов на входной ленте, состояиую из символа под головкой и всех символов, расположенных вправо от него. Эти два элемента информации дают мгновенное описание конечного автомата, которое мы будем называть конфигурацией. Определение. Если A1 = (Q, 2, б, q, F) - конечный автомат, то пара [q, w)Qx* называется конфигурацией автомага М, Конфигурация (f/, w) называется начальной, а пара {q, е), где qF, называется заключительной (или допускающей). Такт автомата М представляется бинарным отношением h-ж (или \-~, если М подразумевается), определенным па конфигурациях. Если б((/, а) содержит q, то [q, aw){q, w) для всех 2 *. Это говорит о том, что если М находится в состоянии q и входная головка обозревает входной символ а, то автомат М Может делать такт, за который он переходит в состояние q и сдвигает головку на одну ячейку вправо. Так как автомат М, вообще говоря, недетерминированный, могут быть и другие 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 [21] 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 0.0019 |