Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
ISO
H. Хомский
щих узлы; пути помечены символами из алфавита А. В этом графе узел, помеченный Sy-, соединен стрелкой, помеченной щ, с узлом, помеченным Sh, в том и только том случае, если ((', /, k) есть одна из троек, описывающих поведение автомата. Пример такого графа показан на рис. 3. (Когда мы интерпретируем такие системы как грамматики, тройки играют роль грамматических правил.) Таким образом, конечный автомат может быть представлен произвольным
Поведение автомата описывается тройками (0,6,0), (1,0,1),
(2,1,0), <3,2,1), {4,1,4), (5,1,4), (0,4,3),(7,4,5). (8,5,4), (9,5,5),
(9.5,6). Состояние -So является начальным и конечным состоянием: СОСТОЯНИЯ Si и Ss могли бы быть опушены (и обычно опускаются), так как они не играют никакой роли в порождении предложений.
конечным ориентированным графом, ребра которого помечены символами из А. Идя вдоль графа OtS0 до первого возвращения в S0 по разрешенным путям, мы порождаем предложение #х#, где х— цепочка, состоящая из последовательных символов, помечающих стрелки, пройденные нами в этом пути.
Для наших целей несущественно представление автомата как источника, порождающего предложение символ за символом при Движении от состоятня к состоянию, или как читающего устройства,
Формальные свойства грамматик
131
переходящего из состояния в состояние, когда оно воспринимает каждый последовательный символ допускаемого им предложения. Это зависит просто от интерпретации обозначений. В любом из этих двух случаев для вышеописанных систем справедливо следующее определение предложения.
Определение 1. Цепочка символов х есть предложение, порождаемое конечным автоматом F, тогда и только тогда, когда существует последовательность символов (ар,,..., арг) в алфавите автомата F и последовательность состояний (STl,..., Sir+i) автомата F, татя, что: 1) Ті=ї'-+і =0; 2) т, =^=O для 1<і<л+1;
3)(р?, Yi, Y(+i) является правилом F для каждого і (1 <^'</);
4) х=#а?1... арг #.
Любое множество предложений, порождаемое конечным яитомя-томГбудем называть региляоным языком. Термин, более принятый в литературе для этих множеств,— это регулярные события (см. работы [30, 53]; эквивалентность различных формулировок была доказана в работах [5, 141).
Заметим, что механизм M движется влево при каждом переходе из состояния в состояние, что единичный символ а„ может занимать клетку на ленте и что команда (i, /, k) применима к M тогда и только тогда, когда он находится в состоянии S1 и читает символ а;. Эквивалентно можно было бы условиться, что а0 не может занимать клетку на ленте, что команда (і, /, k) применима, когда M находится в состоянии Sj и когда либо і — 0, либо M читает символ аь и что лента движется влево только тогда, когда применяется команда (/,k), где іф0. В этом случае команда (0, /, k) может быть истолкована как позволяющая переход из S1 в Sk независимо от входного символа и без движения влево входной ленты. Отметим, что при такой формулировке механизм M будет блокирован, только если он находится в состоянии Sj и наблюдает символ а,, для которых он не имеет команды (i, j, k), и если он, кроме того, не имеет команды (0, /, k).
Приводя предложения, порожденные этими или другими видами автоматов, мы обычно будем опускать граничный символ th
Два конечных автомата эквивалентны^если они порождают один и тр-Гж^язык. Автомат называется детерминированным, если не существует двух команд (i, /, k) и (/, j, I), где кфі, и не существует команды (0, j, k), где ?=jt0 (т.е. пустой переход возможен только при возвращении в S0). Состояние детерминированного автомата однозначно определяется (за исключением возможного возврата в S0) цепочкой символов, воспринятой им на входе, и состоянием, с которого он начал свою работу. Имеется много результатов, относящихся к этим автоматам. Приведем без доказательства две теоремы, которые понадобятся нам в дальнейшем [13, 53].
132
Н. Хомский
Теорема 1 .По заданным конечным автоматам F1, Fi можно построить конечные автоматы G1, Gi, G3, такие, что G1 есть детерминированный автомат, эквивалентный F1, Gi допускает те и только те цепочки, которые отбрасывает (т. е. не допускает) F1, a G3 допускает в точности те цепочки, которые допускает F1 или F2.
Следовательно, множество всех регулярных языков в заданном алфавите А образует булеву алгебру. Заметим к случаю, что для детерминированных автоматов можно было бы вообще избежать появления «пустого» перехода, переформулировав «допустимость цепочки х» в терминах прихода устройства в одно из множества выделенных конечных состояний вместо возвращения в начальное состояние. Эти два определения остаются эквивалентными, если только допустить любое число конечных состояний.
Самый важный результат, касающийся регулярных языков, — это Теорема Клини о структурной характеризации [зи1. Зта тео-6ёмЗ~утверждает, что все (и только) регулярные языки могут быть получаГы из конечных языков с помощью нескольких простых'тео-рётжо-ми5жественных операцийТ Теорема;- таким~6бразом7~даёт простой и естественный 'способ представления любого регулярного языка Tl Л. 4(11. " -——---------------- --------—
