Главная Промышленная автоматика.

Язык называется регулярным, если его можно представить регулярным выражением. Два регулярных выражения аир называют эквивалентными (и пишут а=Р), если они представляют одно и то же множество. Например, (0+1)* =(0*1*)*.

Понятие детерминированного конечного автомата было введено в гл. 4. Его можно воспринимать как устройство, состоящее из блока управления, который всегда находится в одном из конечного числа состояний, и входной ленты, которая просматривается слева направо своей головкой (входной головкой). Детерминированный конечный автомат выполняет "шаги", определяемые текущим состоянием его блока управления и входным символом, обозреваемым входной головкой. Каждый шаг состоит из перехода в новое состояние и сдвига входной головки на одну клетку вправо. Оказывается, что язык представим регулярным выражением тогда и только тогда, когда он допускается некоторым конечным автоматом.

Важным обобщением рассматриваемого понятия является недетерминированный конечный автомат. Для каждого состояния и каждого входного символа недетерминированный автомат имеет нуль или более вариантов выбора следующего шага. Он может также выбирать, сдвигать ему входную головку при изменении состояния или нет.

Определение. Недетерминированным конечным автоматом (НКА) называется пятерка (S, /, б, So, F), где

1) S - конечное множество состояний устройства управления;

2) / - алфавит входных символов;

3) б - функция переходов, отображающая Sx(/ и {е}) в множество подмножеств множества S;

4) So б S - начальное состояние устройства управления;

5) f sS - множество заключительных (допускаюш,их) состояний.

Мгновенным описанием (МО) НКА Л1 называется пара (s, w), где sgS - состояние блока управления и wI* - неиспользованная часть входной цепочки (т. е. символ, обозреваемый входной головкой, и все символы справа от него). Начальным МО автомата М называется МО, у которого первой компонентой служит начальное состояние, а второй - распознаваемая цепочка, т. е. (so, w) для некоторой цепочки ш б /* • Доцускаюи{ие МО - это МО вида (s, е), где sF.

Представим шаги НКА бинарным отношением \- на множестве мгновенных описаний. Если S (s, а) содержит s, то пишут (s, aw) \- (s, w) для всех wI*. Заметим, что а - это или е, или символ из /. Если а=е, то состояние изменяется независимо от обозреваемого входного символа. Если афе, то символ а должен стоять в очередной клетке входной ленты, а входная головка сдвигается на одну клетку вправо.



.Вход Состояние

{Si,

{Ss\

«4

Рис. 9.1. Функция переходов 6.

Рефлексивное и транзитивное замыкание отношения - обозначается через -*. Говорят, что цепочка w допускается автоматом М, если (so, w)\-* (s, е) для некоторого s б Иными словами, входная цепочка w допускается автоматом М, если найдется последовательность из нуля или более шагов, переводящая М из начального МО (so, w) в допускающее МО (s, е). Множество цепочек L{M), допускаемых автоматом М, называют языком, допускаемым автоматом М.

Пример 9.2. Рассмотрим недетерминированный конечный автомат М, допускающий все те цепочки из символов а и Ь, которые оканчиваются цепочкой aba, т. е. L(M)=(a+b)*aba. Пусть М = =({si. Si, Sa, Si}, {a, b), 6, Si, {Si}), где функция б определена на рис. 9.1. (Здесь без е-переходов можно обойтись.)

Пусть на вход автомата М подается цепочка ababa. Тогда М может сработать в соответствии с последовательностями МО, показанными на рис. 9.2. Так как (Si, ababa)}-* (si, е) и S4 - заключительное состояние, то цепочка ababa допускается автоматом М. □

С каждым ИКА связан ориентированный граф, естественным образом представляющий функцию переходов этого автомата.

Определение. Пусть M=(S, I, б, So, F) - НКА. Графом переходов (или диаграммой) автомата М называют ориентированный граф G=(S, Е) с помеченными ребрами. Множество ребер Е и метки определяются следующим образом. Если б (s, а) содержит s для некоторого а1 и {в}, то ребро (s, в) принадлежит Е. Меткой ребра

(si, ababa)

- (Sf, aba) - .

(2, baba)

(St, ba)

-[$ъ,аЬа)

Рис. 9.2. Последовательность МО для входа ababa.




Рис. 9.3. Граф переходов для примера 9.2.

(s, s) служит множество тех bI [}{&}, для которых б (s, Ь) содержит s.

Пример 9.3. Граф переходов для НКА М из примера 9.2 изображен на рис. 9.3. Заключительное состояние обведено двойным кружком. □

Диаграммы НКА и задачи о путях на графах можно связать с помощью определенного замкнутого полукольца. Пусть / - алфавит; положим S/=((/*), и, •, 0, {е}). Из разд. 5.6 известно, что Sy-замкнутое полукольцо, в котором (/*) - множество всех языков над 1,0 - единичный элемент относительно объединения и и {е} - единичный элемент относительно конкатенации •

Теорема 9.1. Всякий язык, допускаемый недетерминированным конечньш автоматом, регулярен.

Доказательство. Пусть M={S, I, б, So, F) - НКА и G=(S, Е) - его диаграмма. Алгоритм 5.5 может найти для каждой пары узлов S и s диаграммы язык Lj,, являющийся множеством всех цепочек, помечающих пути из s в s. Метка каждого ребра диаграммы является регулярным выражением. Более того, если множества C?f \ вычисленные алгоритмом 5.5, представимы регулярными выражениями, то в силу строки 5 этого алгоритма множества С?, также представимы регулярными выражениями. Следовательно, каждый язык Lss можно представить регулярным выражением, а потому он регулярен. " Тогда L(M)= и Ls„s - регулярное множе-

ство, ибо по определению объединение регулярных множеств регулярно. □

Теорема, обратная к теореме 9.1, также верна. Иными словами, для данного регулярного выражения найдется НКА, допускающий язык, представленный этим регулярным выражением.





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 102 103 104 105 106 107 108 109 110 111 112 113 114 [115] 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0038