Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 28
Текст из файла (страница 28)
(г — множество заключительных состоянии. Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управлягощего устройства н входным символом, обозреваемым в данныи момент входной головкой. Сам шаг состоит из изменения состояния и сдвига входной головки иа одну ячейку вправо. Для того чтобы определить будущее поведение конечного автомата, нужно знать лишь (1) текущее состояние управляющего устройства н (2) цепочку символов па входной ленте, состоящую из символа под головкой и всех символов, расположенных вправо от него.
Эти два элемента информации дают мгновенное описание конечного автомата, которое мы будем называть конфигурацией. Определение. Если М =- Я, Х, 6, д„у) — конечный автомат, то пара (д, ш) баххх.' называется конфигурацией автомата М. Конфигурация (у„ы1) называется начальной, а пара (д, е), где ЧЕ г, называется заключительной (или допускающей).
Такт автомата М представляется бинарным отношением '> — м (или ~ —, если М подразумевается), определенным па конфигурациях. Если 6(д, а) содержит д', то (д, гкп) ~ — (д', щ) для всех игЕУ '. Это говорит о том, что если М находится в состоянии у и входная головка обозревает входной символ а, то автомат М может делать такт, за который он переходит в состояние а' и сдвигает головку на одну ячейку вправо.
Так как автомат М, вообще говоря, недетермипированный, могут быть и другие !35 ГЛ. З. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ З.З. РЕГУЛЯРНЫЕ МНОЖЕСТВА, ИХ РАСПОЗНАВАНИЕ И ПОРОЖДЕНИЕ состояния, отличные от Ч', в которые оп тоже может перейти за один такт. Запись С ) — 'м С' означает, что С вЂ” —.. С', а С, ! — М» С, (для й~)1)— что существуют такве конфигурации С„..., С» „что С; ! — м Сз з для всех 0(!< к. С! — м С' означает, что С) — м» С' для некоторого !з ~ 1, а С )-м С' — что С ',— м» С' для некоторого й ~) О. Таким образом, отношения ) — м и ) — м являются соответственно транзитивиым и рефлексивно-транзитивиым замыканием отношения ) — и, Будем опускать нижний индекс М там, где это ие приведет к недоразумениям.
Говорят,что автоматМ допускает цепочку Гв,если (а„цз)! — "(Ч,е) для некоторого Ч Е Р. Языком, определяемым (распознаваемым, допускаемым) автоматом М (обозначается 1. (М)), называется множество входных цепочек, допускаемых автоматом М, т. е. !,(М)=(Ш!1ЭЕ2* И (д„цз) 1 — *(д, Е) дЛя ИЕКОтарОГО ЧЕГ) Пример 2.11, Пусть М вЂ” --((р, д, Г), (О, 1), б, р, (Г)) — конечный автомат, где б задается табл. 2.1. Табяици 2.1 Вход () (з) (з) Состояние р Ч М допускает все цепочки нулей и единиц, содержащие два стоящих рядом нуля.
Начальное состояние р можно интерпретировать так:,два стоящих рядом нуля еще ие появились и предыдущий символ ие был нулем'. Состояние д означает, что „два стоящих рядом нуля еще ие появились, но предыдущий символ был нулем". Состояние Г означает, что „два сто»пц»1х рядом нуля уже появились". Заметим, что, попав в состояние Г, автомат М остается В этом состоянии, Для входа 01001 единственной возможной последовательностью конфигураций, начинающейся конфигурацией (р, 01001), .1ХВ Приведем два примера конечных автоматов, Первый — простой ндетерминироваииый" автомат; второй пример показывает использование недетермииизма. будет (р, 01001) ) — (д, 100!) ) — (р, 001) !†(Ч, 01) )- (Г, 1) )- (Г, е) Таким образом, 01001 ц !.(М). (З ) Пример 2.12.
Построим недетерминированный конечный автомат, допускающий цепочки в алфавите (1, 2, 3), у которых последний символ цепочки уже появлялся в пей раиыпе. Иными словами, цепочка !21 допускается, а 31312 в иет. Введем состояние Ч„ смысл которого в том, что автомат в этом состоянии не пытается ничего распознать, он (нли какой-то его экземпляр) находится в так называемом нейтральном состоянии.
Введем также состоЯниЯ Ч„Ч» и Ч„смысл котоРых в том„что они „делают предположение" о том, что последний символ цепочки совпадает с индексом состояния. Кроме того, пусть будет одно заключительное состояние др Находясь в состоянии Ч„автомат может остаться в ием илн перейти в состояние Ч„если а — очередной символ. Находясь в состоянии Ч„, экземпляр автомата может пеРейти в состоЯние Чр если видит символ а. Из состоЯ- иия д! автомат никуда нс переходит, так как вопрос о том, допускается ли входная цепочка, решается один только раз, Тибяици 2.2 Вход 2 ! 3 (Чз Чз) (Ч') (Чз) (Чз Ч!) (Ч, Чз) (Ч) (Ч, Ч!) (Чз) (Ч Чз) Ч Ч!) Чз) (Чз) Состояние Ч, Чз Чз Ч! 137 когда автомат сочтет входной символ ипоследннм".
Формально автомат М определяется как пятерка М =-((Ч„Ч„Ч„Ч„Ч!), (1, 2, 3), б, Ч, (Ч!)) где 6 задается табл. 2.2. Процесс порождения конфигураций для входа 12321 показан на рис. 2.2. ГЛ. И. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ Так как (о„12321) ) — '(ом е), то 12321 ЕЕ(М), Заметим, что некоторые конфигурации на рис, 2.2 повторяются. Поэтому для представления конфигураций, в которые попадает автомат М, по-видимому, больше подходит ориентированный ациклический граф. (й> 12о21 (й~2з21 ро )21 1И21)~-Сро,1)с(ео,е) )и-( )~-( * г 1)(ог~е) чи 21) (21,1)-<дъе) а~ 321)-(Ои 21)с 9и, 1)-<2ье) '9р 1) йи2)21)-(т1 221)-(ри21) — ((гы1 вые) (фпе) Рис.
2.2. Коифигурации автомата М. 2.2. РЕГУЛЯРНЫЕ МНОЖЕСТВА, ИХ РАСПОЗНАВАНИЕ И ПОРОЖДЕНИЕ языков, определяемых полностью определенными детерминированными конечными автоматами. Сейчас мы это докажем. Соглашение. Так как нам придется рассматривать в основном детерминированные, конечные автоматы, мы будем писать 6 (о, а).— р вместо 6(д, а) ==. (р), когда автомат с функцией пере- а Пииичи 2.И Часто бывает удобно графическое представление конечного автомата.
Определение, Пусть М=(1Е, А, 6, д„Р) — недетермииированный конечный автомат. Диаграммой (илн графом переходов) автомата М называют неупорядоченный помеченный граф, вершины которого помечены именами состояний и в котором есть дуга (рд), если существует такой символ а Е Х, что д Е 6 (р, а). Кроме того, дуга (р, о) помечается списком, состоящим из таких а„ что об 6(р, а). На рис. 2.3 показаны диаграммы автоматов из примеров 2.11 и 2.12.
Начальное состояние указывается иа диаграммах направленной в него стрелкой, помеченной словом „начало", а заключительные состояния обводятся кружком. Определим детерминированный конечный автомат как частный случай недетерминированиого. Определение. Пусть М =- (1), Х, 6, а„р) — недетермниироваиный конечный автомат. Назовем автомат М детерминированным, если множество 6(о, а) содержит не более одного состояния для любых дЕ1;) и аЕХ. Если 6(г), а) всегда содержит точно одно состояш1е, то автомат М назовем полностью определенным. Таким образом, автомат из примера 2.!1 — полностью определенный детерминированный конечный автомат.
В дальнейшем конечным автоматом будем называть полностью определенный детерминированный конечный автомат. Один из наиболее важных результатов теории конечных автоматов состоит в том, что класс языков, определяемых недетерминированными конечными автоматами, совпадает с классом 1ЗВ «ииьа В лиичии 2Л2 Рис, 2.3. диаграммы автоматов. ходов 6 детерминированный. Если 6(о, а)=-1Р), то часто будем говорить, что 6 (о, а) не определено. Теорема 2.3. Если Е=Е (М) для некоторого недетерминированного конечного автомата М, то Е=Е(М') для некоторого конечного автомата М', Дока за тел ь ство. Пусть М=((г, Х, 6, о„р). Построим М'=((г' Х, 6', г),', Р') следующим образом: (1) 9'=-У(()), т.
е. состояниями автомата М' являются множества состояний автомата М; (2) 2о=(чи)' (3) Р' состоит из всех таких подмножеств 5 множества (г, что ЕДЕ~Я; (4) 6(З, а) =Е' для всех Бс:-1е, где 5'=(р ~ 6(о, а) содержит р для некоторого ВЕЗ). гл. а. элементы теогии языков ал. гвгттлягиыв множвствы их гаспознквзнис и погождв низ Оставляем в качестве упражнения доказательство ипдукцией по ! утверждения (2.2.16) (Я, ю) ! — й,(Б', е) тогда и только тогда, когда Б'=(р !(у, ю) ) — и (р, е) для некоторого убей. Отсюда, в частности, следует, что ((аа), !и) ) — Й, (Я', е) для некоторого Я ЕР' тогда и только тогда, когда (д„ю) ) — 'а,(р, е) для некоторого р Е Р.
Итак, 1. (М') = Е (М). П Пример 2.13. Построим конечный автомат М'=(!г, (1, 2, 3), 6', (а„), Р), допускающий язык Е (М), определяемый автоматом М из примера 2.12. Так как М имеет 5 состояний, то, казалось бы, М' должен иметь 32 состояния. Однако не все оии достижимы из начального состояния, Состояние р называется дсстиакимыат, если существует такая цепочка ав, что (д„ае) ',— '(р, е), ааау ! 2 3 Рао. 2.4, Функаиа переколов автомата 44". где да — начальное состояние. Мы будем строить только достижимые состояния. Начнем с замечаииЯ, что состоЯние (д„) достижимо. 6' ((а)а), а)= = — (Ч„д.) для а=1, 2 и 3. Рассмотрим состояние (а„пт). Имеем 63((ч„д,), 1)=(а„а„аг). Продолжая в том же духе, получаем, что множество состояний автомата М (оно является состоянием автомата М') .достижимо тогда и только тогда, когда (1) оно содержит да и (2) если оно содержит д, то содержит также и дю да или да.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
