Сообщение каноническая система , как созданные Эмиль Post , это строка-манипуляция система , которая начинается с конечно-много строк и многократно трансформирует их, применяя конечное множество J заданных правил той или иной форме, создавая тем самым формальный язык . Сегодня они имеют в основном историческое значение, потому что каждая каноническая система Post может быть сведена к системе переписывания строк (система полутуэ), что является более простой формулировкой. Оба формализма полны по Тьюрингу .
Определение
Сообщение каноническая система представляет собой триплет ( , я , R ), где
- A - конечный алфавит, и конечные (возможно, пустые) строки на A называются словами .
- I - конечный набор начальных слов .
- R - это конечный набор правил преобразования строк (называемых производственными правилами ), каждое правило имеет следующую форму:
где каждый g и h - заданное фиксированное слово, а каждый $ и $ ' - переменная, обозначающая произвольное слово. Строки до и после стрелки в продукционном правиле называются антецедентами и следствием правила соответственно. Требуется, чтобы каждый $ ' в консеквенте был одним из $ s в антецеденте этого правила, и чтобы каждый антецедент и консеквент содержали по крайней мере одну переменную.
Во многих контекстах каждое производственное правило имеет только одно предшественник, таким образом принимая более простую форму.
Формальный язык , порожденный каноническая системой Post есть множество, элементы которого являются начальными словами вместе со всеми словами , получаемыми из них путем многократного применения правил производства. Такие наборы рекурсивно перечислимые языков и каждый перечислимый языком является ограничением некоторого такого набора к югу алфавиту A .
Пример (выражения в квадратных скобках)
Алфавит: {[,]}Начальное слово: []Правила производства: (1) $ → [ $ ](2) $ → $$ (3) $ 1 $ 2 → $ 1 [] $ 2Получение нескольких слов на языке правильных скобочных выражений: [] начальное слово [] [] от (2) [[] []] от (1) [[] []] [[] []] по (2) [[] []] [] [[] []] по (3) ...
Теорема о нормальной форме
Постканоническая система называется нормальной, если она имеет только одно начальное слово и каждое производственное правило имеет простую форму
Пост 1943 года доказал замечательную теорему о нормальной форме , которая применима к наиболее общему типу канонической системы Поста:
- Для любой канонической системы Поста на алфавите A , каноническая система Поста в нормальной форме может быть построена из нее, возможно, расширяя алфавит, так что набор слов, содержащих только буквы A , которые порождаются системой нормальной формы, в точности набор слов, порожденный исходной системой.
Системы тегов , которые составляют универсальную вычислительную модель, являются яркими примерами системы нормальной формы Поста, которая также является моногенной . (Каноническая система называется моногенной, если для любой строки можно создать не более одной новой строки за один шаг, т. Е. Система является детерминированной.)
Системы перезаписи строк, формальные грамматики типа 0
Система перезаписи строк - это особый тип канонической системы Post с одним начальным словом, каждое из которых имеет форму
То есть каждое производственное правило - это простое правило подстановки, часто записываемое в форме g → h . Было доказано , что любая каноническая система Post сводится к такой системе замещения , которая, как формальной грамматики , также называется фразовым структура грамматики , или типа 0 грамматики в иерархии Хомского .
Рекомендации
- Эмиль Пост , «Формальные редукции общей комбинаторной задачи принятия решений», American Journal of Mathematics 65 (2): 197-215, 1943.
- Марвин Мински , Вычисления: конечные и бесконечные машины , Prentice-Hall, Inc., Нью-Джерси, 1967.