Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 27
Текст из файла (страница 27)
Из уравнения (2.2.15) видно, что каждая цепочка, принадлежащая 1,(Л,), принадлежит 1, (А,). Это вытекает из того, что любую цепочку ю ~ а,;а;|а|„ можно представить в виде югн! ... |в,„, где ш,Еа,|, и„,~да|А и ю,„..., ш ! Е ага Таким обРазом, цепочка ш ЯвлЯетсЯ конкатенацией последовательности цепочек, каждая из которых принад- |ЗО и|=го, ... |о„, где для некоторой последовательности чисел выполнены условия ю„, ~ а; в иа|ьб а;;„для 1 в-.й<т и 1,= !. Так как у — решение, то д(Х ) =ахи 11а||у(Х!) В... 0а;„д(Х„) для всех 1 В частности, а,,~д(ХА) н ауьй(ХА) с.=д(Х ) для всех 1 и й.
Тогда гв бу(Х! ), гв„,го ей(Х;,) и т. д. В конечном счете получаем, что цепочка го=|о,ш, ... |о„принадлежит множеству у(ХА) =у(Х!). Пришли к противоречию, так как предположили, что ю не принадлежит д(Х|). Таким образом, заключаем, что ) (Х!)~у(Х!) для всех !'. Отсюда непосредственно следует, что 1 — наименьшая неподвижная точка системы 1г. (З Лемма 2.4. Пусть (гл и |гл — системы уравнений до и после одного применения шага 2 алгоритма 2.1. Тогда Ц! и |г., имеют одну и ту же наименьшую неподвижную тансу.
Доказательство. Допустим, что на шаге 2 рассматривается уравнение .4, =-аи+аиА|+ аг, !+!А|+! ~-... + х;„.4„ лежит множеству, обозначаемому некоторым коэффициентом системы (г„и индексы этих коэффициентов удовлетворяют условию леммы 2.3. Аналогично для цепочек, принадлежащих аА|а,*|а|,. Так можно показать, что ),(АА) =1|(А,). Чтобы доказать обратйое включение, предположим, что гвй1|(АА). Тогда по лемме 2.3 ш — ш, ... |в„, где для некоторой последовательности ненулевых индексов 1„..., 1„выполнены условия гв„Еа! о и горба! ! для 1~р(гп и 1,=-/.
Можно И3 однозначно сгруппировать цепочки юг так, чтобы былогв=у!...у„ где у𠆆и! ... ю, и (1) если 1|(!', то в=1+1, (2) если 1|> |, то з выбирается так, чтобы Все 1,+„..., 1, были равны ! и 1,э,на П Отсюда следует, что в любом случае у — коэффициент при А! г л+! в уравнении для Л|, системы 9„и, значит, гвС(,(Л ). В итоге получаем, что 1|(А,) — ~,(ЛА) для всех 1. (З Лемма 2.5. Пусть 1;|, и |;|,— системь! уравнений до и после одного применения шага 5 алгоритл|а 2.1. Тогда |г! и (ге имеют одну и ту же наимень|иую неподвижную точку. Д о к а з а т е л ь с т в о.
Доказательство аналогично доказательству леммы 2.4 и остается в качестве упражнения. (З Теорема 2.1. Алгоритл! 2.! находит наименьшую неподвижную точку стандартной системы уравнений. Доказательство. После того как шаг 5 применен для всех |, все уравнения принимают вид Х,=ао где а; — регулярное выражение в алфавите г. Ясно, что отображение Г, для которого 1(Х,) =-а|, и будет наименьшей неподвижной точкой этой системы. 2.2.2. Регулярные множества н лрвволинейные грамматннн Покажем, что язык определяется праволинейной грамматикой тогда и только тогда, когда он является регулярным множеством. Чтобы доказать, что для каждого регулярного множества существует праволинейная грамматика, начнем с некоторых наблюдений.
Пусть 2 — конечный алфавит. Лемма 26 Множества (1) 8 (В)(е) и (111)(а) для всех акт явля|отея праволинейными языками. Док аз а тел ь ство. (1) 6=((О), А, З, 3) — праволинейная ГРамматика, для которой (. (6) = |д'. 131 ГЛ. й. ЭЛЕМЕНТЫ ТРОРИИ ЯЗЪ|КОЗ гл. РВГуляРные мнОжестВА, их РАспозиАВАние ипОРОждение (й) 6=((5), гь (5- в), 5) — праволииейная грамматика„для которой Е (6) =(г).
(5 а) 5) — праволинейная грамматика, д, которой Е(6.) =-(а). Д Лемма 2.7. Если Е, и Г.,— праволингйныг языки, то языки (1) Е, 0 Е„(!1) Е4Е, и (!!!) 1:, тоже праволингйныг. Доказательство. Так как языки Е, и Е, праволиней- ные, можно считать, что существуют праволинейпые грамматики 64=-(1Ч„Е, Р„5,) и 64=(1~„Е, Р„5,), для которых Е(64)=Е4- и Е(6,) =Е,. Будем также предполагать, что алфавиты Х, и 7т, не пересекаются. Так как иетерминалы грамматики можно как угодно переименовывать, это предположение ие приведет к потере общности. (!) Пусть б,— праволинейная грамматика (Н,(1~т,()(5,), Е, Р,ЦР,()(5,-5,15,), 5,) где 54 — новый нетерл4ииальный символ, не принадлежа1ций ни Н„ ии )А(,.
Ясно, что Е (6,) = Е (6„) 0 Е (6,), так как для каждого вывода 54=:;>о,ш существует либо вывод 54~~о,ш, либо вывод 54=>о+',а4, и обратно. Так как 6,— праволинейная грамматика, то Ь(64)— праеолинейный язык. (Д) Пусть 6, — праволииейная грамматика (4дд!1)А)„ Е, Р„ 5,), в которой Рд определяется так; (!) Если А — хВ принадлежит Р„ то А - хВ принадлежит Р,. (2) Если А — х принадлежит Р„то А- х5, принадлежит Р4. (3) Все правила из Р, принадлежат Р,. Заметим, что если 5, =Фо, ш, то 5, «>~о, и45„а если 54 —,до,х, то 5, =О~„х.
Таким образом, Е (6,) Е (6,) «Е, (6,). Предположим теперь, что 5,=->о,и4. Так как в Р4 цет правил вида Л вЂ” х, которые попали туда из Р„то этот вывод можно записать в виде 5,=:;>в,х5, =-~~о, ху, где и4=-ху и все правила, используе- мые в выводе 5,=>о,х5„попали в Р, с помощью шагов (1) и (2). Следовательно, должны быть выводы 54~~о,х и 5,,4,у. Отсюда Е(6,) «Е(6,) 4. (6,). Итак, ь(64) =ь(6,)4.
(6,), (ш) Пусть грамматика 6, =д (Нд П (54), Е, Р„5,) такова, что 54 не принадлежит 11„а Р, строится следующим образом: (1) Если А — хВ принадлежит Р„то А — хВ принадлежит Рд, (2) Если А — х прннадлсжиг Р„то А — х5, и А — х принадлежат Р,. (3) 5„5,!е принадлежат Р,.
133 Доказательство того, что 54 ~в, Х,5, — >о,х4Х45, =>о, ° . 4 4- Х4Х4 Хд 4~4 Фо Х4Х4 Хд 4Хд ТОГДЭ И ТОЛЬКО ТОГДЕ когда 5,=>в, х„5, г>с,х,,..., 5,=>о', хд, оставляем в качестве упражнения. Отсюда заключаем, что Е(6,)- — -(Е(6,))'. Д Теперь можно доказать, что класс праволипейных языков совпадает с классом регулярных множеств. Теорема 2.2. Язь4к является регулярнь4л4 лгножгствол4 тогда и только тогда, когда он праволингйный. Д оказ а тельство. Необходил4ость. Эта часть доказательства получается из лемм 2.6 и 2.7, если воспользоваться нидукцией по числу шагов построения регулярного множества, где один шаг — это применение одного из правил, определяющих регулярные множества. Досталпочность.
Пусть 6 =-(Х, 5, Р, 5) — праволинейиая грамматика и Н=(А„..., А„). Можно построить стандартную систему уравнений с регулярными коэффициентами, неизвестными которой служат нетермнналы из Х. Уравнение для А, имеет вид А;=-4хгд-! анЛ4-1-... +аьдА„, где (!) а4,=ш,+... -1-4оь если А; и~,! ... !Е44 — все правила с левой частью А, и правой частью, состоящей только из терминалов (если й=О, полагаем аы-— — 8); (2) для 1 > О и;, =- х, +...
+х„, если А,. — х,АГ (... ! х Ау— все правила с левой частью Л; и правой частью, оканчиваю- ЩейсЯ на Лл (как и Раньше, если т= — О, то ы;, = 421). С помощью леммы 2.3 можно показать, что Е(б) =Г'(5), где à †наименьш неподвижная точка построенной системы уравнений (это предлагаем в качестве упражнения). Но алгоритм 2.1 строит 1(5) как язык, обозначаемый некоторым регулярным выражением. Таким образом, Е (6) — регулярное множество. Д Пример 2.10.
Пусть грамматика б определяется правилами 5 — ОА) 15!е А — ОВ) 1А  — 05 !1В Тогда соответствующая система уравнений получается из системы примера 2.9, если Х„Х„Х, заменить соответственно иа 5, А, В. Е(6) — это мнолсество цепочек, в которых число нулей делится на 3. Нетрудно показать, что это множество обозначается регулярным выражением (2.2,3). Д 133 ГЛ. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ 2,2. РЕГУЛЯРНЫЕ М110ЖЕСТНА, ИХ РАСПОЗНАВАНИЕ И ПОРОЖДЕНИЕ 2.2.3.
Конечные автоматы Мы рассмотрели три способа определения класса регулярных множеств: (1) класс регулярных множеств — наименьший класс языков, содержащий множества йу, (е) и (а) для всех символов а и замкнутый относительно операций объединения, конкатенации и итерации; (2) регулярные множества †множест, определяемые регулярными выражениями; (3) регулярные множества — языки, порождаемые праволинейными грамматиками. Теперь опишем четвертый способ их Определения с помощью конечных автоматов. Конечный автомат является одним из про- СтсйШИХ РаСПОЗНаВатЕЛЕй.
яБЕСКОИЕЧНОй" ПаМЯтИ У НЕГО НЕт. Обычно конечный автомат состоит только из входной ленты и управляющего устройства с конечной памятью. Здесь мы позволим управляющему устройству быть @едетерминированным, но входная головка будет односторонней, Фактически мы потребуем, чтобы входная головка сдвигалась вправо на каждом такте '). Двусторонний конечный автомат рассматривается в упражнениях. Мы определим конечный автомат, задав конечное множество его управляющих состояний, допустимые входные символы, начальное состояние и множество заключительных состояний, т. е, состояний, указывающих, что входная цепочка допускается. Задается также функция переходов состояний, которая по данному „текущему" состоянию и „текущему" входному символу указывагег все возможные следующие состояния. Подчеркнем, что это устройство — недетермииированиое в теоретико-автоматном смысле, т.
е. оно переходит во все свои следующие состояния, если угодно, дублируя себя так, что в каждом из возможных следующих состояний находится один экземпляр этого устройства. Недетсрминированный автомат допускает входную цепочку, если какой-нибудь из его параллельно работающих экземпляров достигает допускающего состояния. Недетермииизм конечного автомата ие следует смешивать со „случайностью", при которой автомат может случайно выбрать одно из следующих состояний с фиксированными вероятностями, но этот автомат всегда имеется только в одном экземпляре. ') Напомним, что пс определснню одяпсторонннй распоанааатель нс сдвигает свою нкпдную Головку влево; ояа, однако, может оставаться неяпданжнпй ,а течение такта.
Если ппанплнть конечному автомату оставлять свою акпдную гплопку неподанжнпн, ягп не даст ему возможности распознать наык, не рас. ппапанасмый обычным консчнын автоматом. 134 Такой автомат называется „вероятностным" и здесь изучаться не будет. Дадим формальное определение иедетерминироваиного конечного автомата. Определение. Недетерминированный конечный автомат — это пятерка М =-(О, гь 6, у„г), где (1) сг — конечное множество состояний; (2) Х вЂ” конечное множество допустимых входных символов; (3) 6 — отображение множества 9х Б в множество У Д), определяющее поведение управляющего устройства; функцию 6 иногда называ1от функцией переходов; (4) д, ~ ь1 — начальное состояние управляющего устройства; (5) г" с=.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
