1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 71
Текст из файла (страница 71)
В этой главе мы увидим, что они полезны для описания идентифицируемых образов. Определение. Пусть ! — алфавит. Регулярные выражения над ! и языки, представляемые ими, рекурсивно определяются следующим образом. 1. 8 является регулярным выражением и представляет пустж множество. 2. е является регулярным выражением и представляет множество (е). 3. Для каждого а Е ! символ а является регулярным выражением и представляет множество (а). 4. Если р и д — регулярные выражения, представляющие множества Р и !Е соответственно, то (р+о), (ро) и (рв) являются регулярными выражениями и представляют множества Р (! !!, РГч и Рв соответственно. При записи регулярного выражения можно опустить многие скобки, если предположить, что операция ' имеет более высокий приоритет, чем конкатенация и +, а конкатенация — более высокий приоритет, чем +, Например, ((0(1Р))+0) можно записать как 0!А+О. Кроме того, вместо ррР будем для краткости писать р+.
Пример 9.!. 1. 01 — регулярное выражение, представляющее множество (01).' 2. (О+!)* представляет (О, 1)*. 3. 1 (О+1)*1+1 представляет множество всех цепочек, начинающихся и кончающихся символом!. П ГЛ. 9. АЛГОРИТМЫ ИДЕНТИФИКАЦИИ Язык называется регулярным, если его можно представить регулярным выражением. Два регулярных выражения а и р называют эквивалентными (и пишут а=р), если они представляют одно и то же множество. Например, (О+1)ь=(0*1*)*. Понятие детерминированного конечного автомата было введено в гл.
4. Его можно воспринимать как устройство, состоящее из блока управления, который всегда находится в одном из конечного числа состояний, и входной ленты, которая просматривается слева направо своей головкой (входной головкой). Детерминированный конечный автомат выполняет "шаги", определяемые текущим состоянием его блока управления и входным символом, обозреваемым входной головкой. Каждый шаг состоит из перехода в новое состояние и сдвига входной головни на одну клетку вправо. Оказывается, что язык представйм регулярным выражением тогда и только тогда, когда он допускается некоторым конечным автоматом.
Важным обобщением рассматриваемого понятия является не- детерминированный конечный автомат. Для каждого состояния и каждого входного символа недетерминнрованный автомат имеет нуль или более вариантов выбора следующего шага. Он может также выбирать, сдвигать ему входную головку при изменении состояния или нет. Определение. Недетерминированным конечным автоматом (НКА) НаЗЫВаЕтея Пятсриа (5, 1, Ь, зы Г), ГдЕ 1) 5 — конечное множество состояний устройства управления; 2) 1 — алфавшп входных символов; 3) Ь вЂ” функция переходов, отображающая о"к'(1 (1 (е)) в множество подмножеств множества 3; 4) э, Е Я вЂ” начальное состояние устройства управления; Ь) Г" с=.З вЂ” множество заключительных (донускающих) состояний. Мгновенным описанием (МО) НКА М называется пара (5, в), где з Е 5 — состояние блока управления и в Е 1ь — неиспользованная часть входной цепочки (т.
е. символ, обозреваемый входной головкой, и все символы справа от него). Начальным МО автомата М называется МО, у которого первой компонентой служит начальное состояние, а второй — распознаваемая цепочка, т. е. (э„ ш) для некоторой цепочки шЕ1*. ДоцускающиеМΠ— этоМО вида (э, е), гдеэЕ Г".
Представим шаги НКА бинарным отношением 1 — на множестве мгновенных описаний. Если Ь(з, а) содержит э', то пишут (5, аю) 1— (5', и) для всех шЕ1'. Заметим, что а — это или е, или символ из 1. Если а=в, то состояние изменяется независимо от обозреваемого входного символа, Если абазе, то символ а должен стоять в очередной клетке входной ленты, а входная головка сдвигается на одну клетку вправо. 35Ь вл. конячиые лвтомлты и вягзлявныя вывлжения | Вход Состояние (з„за) Э (з.) Э (з) (зв) )2) 8 И Э (з1) (з*) Рнс. 9Л. Функция переходов б.
Рефлеисивное и транзитивное замыкание отношения ) — обозначается через ~ — '. Говорят, что цепочка св допускается автоматом М, если (з„св) ( — * (з, е) для некоторого з б г. Иными словамн, входная цепочка св допускается автоматом М, если найдется последовательность из нуля или более шагов, переводящая М из начального МО (з„св) в допускающее МО (з, е). Множество цепочек Е(М), допускаемых автоматом М, называют языком, допускаемым автоматом М. а 6й, деда — (дп аьа) — (лп Ьа) (л» а) — (л~, е) (ло алаЯа) 'ь, и ь..~ 'в;~ (ль Ьааа) — ~ (знала) — в (лм ла) (в„, е) Ряс.
9ЛЬ Последовательность МО для входа аоаьа, 337 Пример 9.2. Рассмотрим недетерминированный конечный автомат М, допускающий все те цепочки из символов а и Ь, которые оканчиваются цепочкой аЬа, т. е. Е(М)=(а+Ь)ваЬа. Пусть М= =((з,„з„з„з,), (а, Ь), б, з„(з,)), где функция б определена на рис. 9.1. (Здесь без е-переходов можно обойтись.) Пусть на вход автомата М подается цепочка аЬаЬа. Тогда М может сработать в соответствии с последовательностями МО, показанными на рис. 9.2.
Так как (з„аЬаба) ~ — в (з„е) и з, — заключительное состояние, то цепочка аЬаЬа допускается автоматом М. С) С каждым НКА связан ориентированный граф, естественным образом представляющий функцию переходов этого автомата. Определение. Пусть М=(Я, ), б, з„г') — НКА. Графом переходов (или диаграммой) автомата М называют ориентированный граф 0=(5, Е) с помеченными ребрами. Множество ребер Е и метки определяются следующим образом.
Если б (з, а) содержит з' для некоторого аЕ)() (е), то ребро (з, з') принадлежит Е. Меткой ребра гл. и алгоритмы идвнтиэнкдции Рис. 9З. Граф переходов дди примера 9.9. (з, з') служит множество тех Ь ~ / 0 (а), для которых б (в, Ь) содержит з'. Пример 9.3. Граф переходов для НКА М из примера 9.2 изображен на рис. 9.3. Заключительное состояние обведено двойным кружком. О Диаграммы НКА и задачи о путях на графах можно связать с помощью определенного замкнутого полукольца. Пусть х — алфавит; положим Вг=(У(Р), О,, 8, (е)).
Из равд. 5.6 известно, что я — замкнутое полукольцо, в котором у(хе) — множество всех языков над 1, (о — единичный элемент относительно обьединения () и (в) — единичный элемент относительно конкатенации ° Теорема 9.!. Всякий язык, допускаемый недетерминированным конечным автоматом, рееулярен. Д о к а з а т е л ь с т в о. Пусть М =(В, 1, 6, з„г) — НКА и б=(Я, Е) — его диаграмма. Алгоритм 5.5 может найти' для каждой пары узлов з и з' диаграммы язык Е„,, являющийся множеством всех цепочек, помечающих пути из з в з'. Метка каждого ребра диаграммы является регулярным выражением.
Более того, если множества С~~ ', вычисленные алгоритмом 5.5, представимы регулярными выражениями, то в силу строки 5 этого алгоритма множества Саи также представимы регулярными выражениями. Следовательно, каждый язык Е„. можно представить регулярным выражением, а потому он регулярен. ' Тогда Е(М)= 0 Е... — регулярное множе- еек ство, ибо по определению объединение регулярных множеств регулярно. П Теорема, обратная к теореме 9.1, также верна. Иными словами, для данного регулярного выражения найдется НКА, допускающий язык, представленный этим регулярным выражением. зза ел. коннчнын автоматы и нвгнляянын ныялжения и Ф и Рис. 9А. Конечные автоматы, допускакнцне языки, представленные регулярныын выражениями длины ): (о) я, (б) (е), (а) (а). С точки зрения сложности вычислений наиболее важно, что можно найти НКА, у которого число состояний не больше удвоенной длины данного регулярного выражения и который из каждого своего состояния может перейти не более чем в два других.
Теорема 9.2. Пусть а — регулярное выражение. Тогда найдется НКА М=(5, 1, б, з„(зт)), допускающий язык, представленный а, и обладающий такими свойствами: 1) йЩ(2)а~, где ~а| — длина выражения а '), 2) для каждого а~1() (и) множество Ь(зт, а) пусто, 3) для каждого з Е 5 сумма чисел йб (з, а)!! по всем а из 1 () (е) не превосходит 2. Д о к а з а т е л ь с т в о. Доказательство проведем нндукцией по длине выражения а. Рассмотрим базис, т. е.
случай (сс(=1. Тогда выражение а должно быть одного из трех видов: (а) йу, (б) в или (в) а для некоторого а Е 1. На рис. 9.4 изображены три автомата, имеющие по два состояния каждый, допускающие указанные языки и удовлетворяющие условиям теоремы. Для шага индукции рассмотрим четыре возможных вида он (а) р+Т, (б) РТ, (в) р', (г) (()), где р и Т вЂ” регулярные выражения. В случае (г) а и р представляют один и тот же язык, так что индукция очевидна.
Рассмотрим другие случаи. Пусть М' и М"— НКА, допускающие языки, представленные выражениями р и у соответственно, причем их множества состояний не пересекаются. Пусть з,' и з," — начальные состояния этих автоматов, а з~ и зг — их заключительные состояния. Графы переходов для случаев (а), (б) и (в) показаны на рнс. 9.5.
Пусть длины а, р и Т равны ~а~, ф~ и |Т~ соответственно, а и, и' и п" — числа состояний автоматов М, М' и М". В случае (а) ~а~= = 3~+(у(+1 и п=п'+п"+2. По предположению индукции и'( <2ф( и и" 2~у(, откуда п<2!а1 Кроме того, в случае (а) добавляются только два ребра, выходящие из з, (которые удовлетворяют тому ограничению, что из любого узла выходит не более двух ребер), да еще по одному ребру, выходящему из каждого узла зг и зь Так ') Длиной регулярного выражения а называется число вхождений символов в цепочку а. Например, )е*!=2. Можно было бы усилить свойство Н игнорируя скобки при подсчете длины выражения о (например, регулярное выражение (о*ь')* при таком условии имело бы длину 5, а не 7). эз9 гл.
е. ллговитмы идннтиьиклции / Ф аг'ВРФ® м" г ) а Рис. 9.5. Графы переходов автоматов, допускающие языки, представленные регулярными выражениями (а) ()+у, (б) ()у, (в) рь. как по предположению из каждого узла зг и з; раньше не выходило ни одного ребра, то это же ограничение на число выходящих ребер выполнится и для зг и зг. Наконец, из з„очевидно, никакие ребра не выходят. Случай (б) проверяется аналогично'). В случае (в) (а)=(()(+1 и л и'+2. Поскольку п'~2(р(, то отсюда следует, что г~2(сс(.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
