Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Приведем эту теорему в несколько отличной формулировке.
Для заданного алфавита А определим рекурсивно понятие представляющего выражения следующим образом.
Определение 2. 1) Каждая конечная цепочка в алфавите А есть представляющее выражение. 2) Если X1 и Xi— представляющие выражения, то X1Xi— представляющее выражение. 3) Если Xi, где суть представляющие выражения, тогда и
(X1,.-.,Xn)*— представляющее выражение.
Это определение задает нам 1) некоторые представляющие выражения, соответствующие цепочкам в Л, и позволяет нам образовывать другие представляющие выражения путем 2) соединения их Друг с другом и 3) разделения их запятой и заключения в скобки, помеченные звездочкой.
Теперь мы должны сказать, что же именно представляют эти представляющие выражения.
Определение 3. 1) Конечная цепочка в Л представляет самое себя (точнее, единичный класс, содержащий только эту цепочку). 2) Если X1 представляет множество цепочек S1, a Xi— множество цепочек S2, то X1Xi представляет множество всевозможных цепочек вида VW, где a W ? S2. 3) Если Xi,
представляют множества цепочек Si, то (X1,...,Х„)* представляет множество всех цепочек V1...Vm, таких, что для tWKdoeo I<j<Jm cyutficmeyem k (I-^k^n), такое, что Ky GSs.
Формальные свойства грамматик
133
Заметим, что, согласно условию 3, представляющее выражение (X1,...,Xn)* задает не порядок, в котором встречаются элементы но только п множеств, из которых они выбраны. Разобраться в смысле определения 3 лучше всего можно, рассмотрев диаграммы
о—-—о
о
(аг аг)
0,(?; аз
О
%
-о
д а,(а2. а3(а4, as)'ae, a7)’ag
Рис. 4. Примеры использования представляющих Dbipjmsний. Слева — представляющие выражения, справа — диаграммы состояний.
состояний или части диаграмм состояний, порождающие представляемые множества цепочек. На рис. 4 случаи 6 ив иллюстрируют образование соединения и операции «звездочка» (т.е. образо-
Н. Хомский
вание выражения (X1......Xn)*. Случай г показывает сочетание этих
операций. Автомат порождает Q1Q3, Q1Q2Qa. Q1Q2O2Q3.... Случай д показывает еще более сложный элемент и т.д.
Теперь уже может быть сформулирована следующая теорема.
Теорема 2. Язык L является регулярным языком тогда и только тогда, когда существуют такие представляющие выражения X1, где 1 что L есть объединение множеств Ei, пред-
ставленных соответственно выражениями X1,...,Xn [13].
Доказательство теоремы основано на том, что для любой диаграммы состояний автомата F можно построить эквивалентную ей диаграмму состояний, представляющую собой сочетание элементов, таких, как на рис. 4; из этой иовой диаграммы непосредственно может быть получено представляющее выражение для языка автомата F. Разумеется, в общем случае при этом получается недетерминированный автомат.
Специальный интересный класс конечных автоматов состоит из автоматов, обладающих тем свойством, что состояние автомата однозначно определяется последними k символами входного предложения. Автомат, для которого существует такое фиксированное k, называется k-ограниченным автоматом, а язык, который он порождает,— k-ограниченным языком.
Допустим, что M есть ^-ограниченный автомат со словарем V, состоящим из D символов. Можно задать его поведение матрицей D4XD1 в которой каждый столбец соответствует элементу W ?V, а каждая строка — цепочке <р длины k, состоящей из элементов V. Соответствующий элемент матрицы будет равен нулю или единице в зависимости от того, допускает ли автомат элемент K71 еслн он уже допустил цепочку <р. Каждая такая цепочка <р определяет состояние автомата.
Это понятие (^-ограниченного автомата) известно в лингвистике в несколько модифицированном виде. Предположим, что элементами определяющей матрицы являются числа между нулем и единицей и каждый элемент представляет собой частоту, с которой в некотором тексте встречается слово, соответствующее заданному столбцу матрицы, при условии что перед этим встретились k слов, определяющие заданную строку матрицы. Эта матрица интерпретируется как описание вероятностного ^-ограниченного автомата, порождающего цепочки в соответствии с заданным множеством вероятностей перехода, т.е. если автомат находится в состоянии, определенном і-й строкой матрицы, что соответствует порожденной последовательности символов Wi1...W1h , то элемент, стоящий в клет-ке (*’. /) і дает вероятность того, что следующее порождаемое слово будет Wj. После того как порождено слово Wt, автомат переходит в состояние, определяемое цепочкой Wii...W1k Wj. При ?>1 такое
Формальные свойства грамматик.
135
устройство порождает так называемое приближение (&+1)-го порядка к тому тексту, из которого были взяты вероятности (см. работы [72, 43]). Мы еще вернемся к этому понятию в разд. 1.2 следующей главы1).
P и с. 5. Конечный автомат, не являющийся ft-ограннченным ни при каком k.
Очевидно, не каждый конечный автомат ^-ограничен. Например, автомат с тремя состояниями, схема которого показана на рис. 5, не является ^-ограниченным ни для какого k. Однако для каждого регулярного языка L существует 1-ограпяченный язык L* и гомоморфизм /, такой, что L—f(L*) [61 ]. Действительно, пусть L допускается детерминированным автоматом M, в котором нет правила (І, у, 0) при ?=/=0 (ясно, что такой M всегда существует). Пусть М* имеет входной алфавит, состоящий из символов (at, SJj, и внутренние состояния Ifli, Sj ], где Ctt есть символ из алфавита М, a Sj есть состояние М, при этом [а0, S0] есть начальное состояние. Переходы автомата M* определяются переходами M по следующему принципу: если (I, j, k) есть правило автомата М, то М* может переходить из состояния [а„ S, ! (при любом I) в состояние IajjSft], если он наблюдает символ (OhSk). Пусть теперь L*—язык, допускаемый автоматом М*. Пусть / — гомоморфизм, отображающий ((Jil Sj) на Qi Для всех І, /. Тогда L=f(L*) и L* есть 1-ограниченный язык.
