Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 21
Текст из файла (страница 21)
Состояние дз соответствует ситуации, когда только что прочитана десятичная точка, а цифры целой части числа либо уже были прочитаны, либо нет. В состоянии д„уже наверняка прочитана хотя бы одна цифра, но еше не прочитана десятичная точка. Таким образом, дз интерпретируется как ситуация, когда мы прочитали десятичную точку и хотя бы одну цифру слева или справа от нее. Мы можем оставаться в состоянии дз, продолжая читать цифры, ио можем н "догадаться", что цепочка цифр закончена, и спонтанно перейти в допускающее состояние чз СЗ Пример 2.17. Метод распознавания множества ключевых слов, предложенный в примере 2.14, можно упростить, разрешив е-переходил Например, НКА на рис. 2.16, распознающий ключевые слова ыеЬ н еЬау, можно реализовать и с помощью епереходов, как показано на рнс.
2.19. Суть в том, что для каждого ключевого слова строится полная последовательность состояний, как если бы это было единственное слово, которое автомат должен распознавать. Затем добавляется новое начальное состояние (состояние 9 на рис. 2.19) с я-переходами в начальные состояния автоматов для каждого из ключевых слов. 1л 2.5.2. Формальная запись е-НКА к-НКА можно представлять точно так же, как и НКА, с той лишь разницей, что функция переходов должна содержать информацию о переходах по к. Формально, е-НКА А можно представить в виде А = (Д, Е, д, г(„, г), где все компоненты имеют тот же смысл, что и для НКА, за исключением д, аргументами которой теперь являются состояние из Д и элемент множества Е Яб), т.е.
либо некоторый входной символ, либо к. Никаких недоразумений при этом не возникает, поскольку мы оговариваем, что к, символ пустой цепочки, не является элементом алфавита Е. Пример 2.18. е-НКА на рис. 2.18 можно формально представить как Е=((йо 9ь" 9з) (., +,—,О, 1, ...,9) б, г)о (9з)) где функция переходов 6 определена таблицей переходов на рис. 2.20. П Рис. 2.20. Та бавч а переходов к рис. 2.
/8 2.5.3. Что такое е-замыкание Дадим формальное определение расширенной функции переходов для в-НКА, которое приведет к определению допустимости цепочек и языков для данного типа автоматов и в конце концов поможет понять, почему ДКА могут имитировать работу к-НКА. Одна- ко прежде нужно определить одно из центральных понятий, так называемое в-заиыкание состояния. Говоря нестрого, мы получаем в-замыкание состояния д, совершая все возможные переходы из этого состояния, отмеченные ж Но после совершения этих переходов и получения новых состояний снова выполняются к-переходы, уже из новых состояний, и т.д.
В конце концов, мы находим все состояния, в которые можно попасть из д по любому пути, каждый переход в котором отмечен символом ж Формально мы определяем г-замыкание, ЕСЬОЕЕ, рекурсивно следующим образом. Базис. ЕСЬОЕЕ(д) содержит состояние д. Индукции. Если ЕСЬОЯЕ(д) содержит состояние р, и существует переход, отмеченный б, из состояния р в состояние г, то ЕСЬОЯЕ(д) содержит г. Точнее, если д есть функ- 2.5. КОНЕЧНЫЕ АВТОМАТЫ С ЭПСИЛОН-ПЕРЕХОДАМИ 91 ция переходов рассматриваемого к-НКА и ЕСЕОЬЕ(д) содержит р, то ЕСЬОБЕ(д) содержит также все состояния из 6(р, а).
Пример 2.19. У автомата, изображенного на рис. 2.18, каждое состояние является собственным г-замыканием, за исключением того, что ЕДОКЕ(с)о) = (йм с!1) и ЕС1-ОЬЕ(9з) = (9л с)з). Это объясняется тем, что имеется лишь два г;перехода, один из которых лобавляет д1 в ЕСЕОЗЕ(до), а другой — 9з в ЕСЕОЯЕ(9з). На рис. 2.2! приведен более сложный пример. Для данного в нем набора состояний, который может быть частью некоторого к-НКА, мы можем заключить, что ЕС1 ОБЕ(1) = (1, 2, 3, 4, 6) . Рис. 2.2А Несколько состолппк в переходов В каждое из этих состояний можно попасть из состояния 1, следуя по пути, отмеченному исключительно ц К примеру, в состояние 6 можно попасть по пути 1 — э2 — >3 — >6.
Состояние 7 не принадлежит ЕСЕОЗЕ(!), поскольку, хотя в него и можно попасть из состояния 1, в соответствующем пути содержится переход 4 — >5, отмеченный не ж И не важно, что в состояние 6 можно попасть из состояния 1, следуя также по пути ! — э4 — >5 — >6, в котором присутствует не я-переход. Существования одного пути, отмеченного только к, уже достаточно для того, чтобы состояние 6 содержалось в ЕСЕОЗЕ(1). П 2.5.4. Расширенные переходы и языки е-НКА С помощью а-замыкания легко объяснить, как будут выглядеть переходы в-НКА для заданной последовательности входных (не-к) символов.
Исходя из этого, можно определить, что означает для к-НКА допустимость входных данных. Пусть Е = (О, Х, 6, сг„р) — некоторый к-НКА. Для отображения того, что происходит при чтении некоторой последовательности символов, сначала определим 6 — расширенную функцию переходов. Замысел таков: определить 6 (9, н) как множество состояний, в которые можно попасть по путям, конкантенации меток вдоль которых дают цепочку нк При этом, как и всегда, символы к, встречающиеся вдоль пути, ничего не добавляют к ж.
Соответствующее рекурсивное определение 6 имеет следующий вид. ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ 92 Базис. б (д, в) = ЕСЬОЗЕ(д). Таким образом, если а — метка пути, то мы можем совершать перехолы лишь по дугам с меткой в, начиная с состояния д; это дает нам в точности то жс, что и ЕСЬОЗЕ(д). Индукции. Предположим, что и имеет вид ха, где а — последний символ и. Отметим, что а есть элемент Х и, следовательно, не может быть е, так как в не принадлежит Е, Мы вычисляем 6 (д, н) следующим образом. 1. Пусть (рь ри ..., рь) есть 6 (д, х), т.с.
р, — это все те и только те состояния, в которые можно попасть из д по пути, отмеченному х. Этот путь может оканчиваться од- ним или несколькими к-переходами, а также содержать и другие а-переходьь 2. Пусть ( )д (рь а) есть множество (гь г,, ..., г ), т.е. нужно совершить все переходы, отмеченныс символом а, из тех состояний, в которые мы можем попасть из д по пути, отмеченному х. Состояния г; — лишь некоторые из тех, в которые мы можем попасть из д по пути, отмеченному в. В остальные такие состояния можно попасть из состояний г; посредством переходов с меткой в, как описано ниже в (3). 3. б (д, и) = 1) ЕСЬОЗЕ(г,). На этом лополнительном шаге, где мы берем замыкание и добавляем все выходящие из д пути, отмеченные и, учитывается возможность существования дополнительных дуг, отмеченных и, переход по которым может быть совершен после перехода по последнему "непустому" символу а.
Пример 2.20. Вычислим б (д,, 5. б) для в-НКА на рис. 2.13. Для этого выполним следующие шаги. ° б (до в) = ЕСЬ05Е(до) = (до, дД. ° Вычисляем б (д,, 5) следующим образом. 1. Находим переходы по символу 5 из состояний д, и дь полученных при вычислении 6 (до, и)' О(до, 5) 0 П(ф 5) = (дь д4) . 2. Находим в-замыкание элементов, вычисленных на шаге (1). Получаем: ЕСЬОЗЕ(д,) 0 ЕСЬО5Е(д4) = (дД 0 (д4) = (дь д,), т.е. множество д (до, 5). Эта двушаговая схема применяется к следующим двум символам. ° Вычисляем 6 (до, 5.). 1. Сначала б(дь .) 0 о(ди ° ) = (дз) 0 (дз) = (дз дз).
2. Затем 6 (ди 5. ) = ЕСЬОЗЕ(дз) 0 ЕСЬОЗЕ(дз) = (дг) 0 (дь дз) = (ди дз, дз) ° Наконец, вычисляем 6 (дм 5. 6). 2.с. КОНЕЧНЫЕ АВТОМАТЫ С ЭПСИЛОН-ПКРЕХОДАМИ 93 1. Сначала д(дз, 6) () 4суз, 6) () д(дз, 6) = (суз) () (г)з) () кз = (1з). 2. Затем б (Еь 5 . 6) = ЕСЬОБЕ(г)з) = (зуз, зуз). Теперь можно определить язык я-НКА Е = (Ь1, Х, 4 з1,, Р) так, как и было задумано ранее: Е(Е) = (и ~ Б (д, зг) П Ри И). Таким образом, язык Š— это множество цепочек и, которые переводят автомат из начального состояния хотя бы в одно из допускающих.
Так, в примере 2.20 мы видели, что б (Ез, 5 . 6) содержит допускающее состояние з1з, поэтому цепочка 5 . б принадлежит языку в-НКА. 2.5.5. Устранение Е-переходов Для всякого к-НКА Е можно найти ДКА 2>, допускающий тот же язык, что и Е. Поскольку состояния Ез являются подмножествами из состояний Е, то используемая конструкция очень напоминает конструкцию подмножеств. Единственное отличие состоит в зом, ч зо нужно присоединить еще и е-переходы Е, применив механизм я-замыкания.
Пусть Е = Яя, Х, ззв, 11я, Рв). Тогда эквивалентный ДКА О=(Уо,Е,Дь 1о,ро) определяется следующим образом. 1. До есть множество подмножеств Дя Точнее, как мы выясним, для 2> допустимыми состояниями являются только а-замкнутые подмножества Дя, т.е.
такие множества Я~ Дя, для которых 5= ЕСЬОЗЕ(Я). Иначе говоря, а-замкнутые множества состояний Я вЂ” это такие множества, у которых всякий к-персход из состояния, принадлежащего Е, приводит снова в состояние из Я. Заметим, что 0 есть к-зам- кнутов множество. 2. озз = ЕСЬОЗЕ(ое), т.е., замыкая множество, содержащее только начальное состояние Е, мы получаем начальное состояние 1>. Заметим, что это правило отличается от использованного ранее в конструкции подмножеств — там за началыюе состояние по- строенного автомата принималось множество, содержащее только начальное со- стояние данного НКА. 3.
гр — это такие множества состояний, которые содержат хотя бы одно допускающее состояние автомата Е. Таким образом, гр = (Я( Япринадлежит Др и ЯП Ря зз О). 4. Дз(Я, а) для всех а из Х и множеств Е из До вычисляется следующим образом: а) пусть Я = (рь рз, ..., рь); б) вычислим ( )Б (р„а); пусть это будет множество (гь гз.. г ); в) тогда Дз(Я, а) = ( ) ЕСЬОЗЕ(гз). з=! ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ Пример 2.21. Удачим я-переходы из в-НКА (см. рис. 2.18), который далее называется Е. По Е мы 'строим ДКА 12, изображенный на рнс. 2.22. Для того чтобы избежать излишнего нагромождения, мы удалили на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
