Постканоническая система

Каноническая система Поста , также известная как система постпроизводства , созданная Эмилем Постом , представляет собой систему манипулирования строками, которая начинается с конечного числа строк и многократно преобразует их, применяя конечный набор j заданных правил определенной формы, таким образом создавая формальный язык . Сегодня они имеют главным образом историческое значение, поскольку любую каноническую систему Поста можно свести к системе переписывания строк (полусистеме Туэ), что является более простой формулировкой. Оба формализма полны по Тьюрингу .

Определение

Пост -каноническая система представляет собой тройку ( A , I , R ), где

• A — конечный алфавит, и конечные (возможно, пустые) строки в A называются словами .
• I — конечное множество исходных слов .
• R — это конечный набор правил преобразования строк (называемых продукционными правилами ), каждое правило имеет следующую форму:

${\displaystyle {\overset {\begin{matrix}g_{10}&\$_{11}&g_{11}&\$_{12}&g_{12}&\dots &\$_{1m_{1}}&g_{1m_{1}}\\g_{20}&\$_{21}&g_{21}&\$_{22}&g_{22}&\dots &\$_{2m_{2}}&g_{2m_{2}}\\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\g_{k0}&\$_{k1}&g_{k1}&\$_{k2}&g_{k2}&\dots &\$_{km_{k}}&g_{km_{k}}\\\end{matrix}}{\underset {\begin{matrix}h_{0}&\$'_{1}&h_{1}&\$'_{2}&h_{2}&\dots &\$'_{n}&h_{n}\\\end{matrix}}{\downarrow }}}}$

где каждый g и h — заданное фиксированное слово, а каждый $ и $’ — переменная , обозначающая произвольное слово. Строки до и после стрелки в производственном правиле называются антецедентами и консеквенциями правила соответственно. Требуется, чтобы каждый $' в консеквенте был одним из $ в антецедентах этого правила и чтобы каждый антецедент и консеквент содержали хотя бы одну переменную.

Во многих контекстах каждое производственное правило имеет только один антецедент, поэтому принимает более простую форму:

${\displaystyle g_{0}\ \$_{1}\ g_{1}\ \$_{2}\ g_{2}\ \dots \ \$_{m}\ g_{m}\ \rightarrow \ h_{0}\ \$'_{1}\ h_{1}\ \$'_{2}\ h_{2}\ \dots \ \$'_{n}\ h_{n}}$

Формальный язык , порожденный канонической системой Поста, представляет собой множество, элементами которого являются исходные слова вместе со всеми словами, которые можно получить из них путем многократного применения правил производства. Такие наборы являются рекурсивно перечислимыми языками, и каждый рекурсивно перечислимый язык является ограничением некоторого такого набора подалфавитом A .

Пример (правильно сформированные выражения в скобках)

Алфавит: {[, ]}Начальное слово: []Правила производства:(1) $ → [ $ ](2) $ → $$
(3) $ 1 $ 2 → $ 1 [] $ 2Образование нескольких слов в языке правильно построенных скобочных выражений: [] начальное слово [][] по (2) [[][]] по (1) [[][]][[][]] по (2) [[][]][][[][]] по (3) ...

Теорема о нормальной форме

Говорят, что каноническая система Поста находится в нормальной форме, если она имеет только одно начальное слово и каждое продукционное правило имеет простую форму.

${\displaystyle g\$\ \rightarrow \ \$h}$

Пост 1943 доказал замечательную теорему о нормальной форме , которая применима к наиболее общему типу канонической системы Поста:

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

Системы тегов , которые составляют универсальную вычислительную модель, являются ярким примером системы постнормальной формы, которая также является моногенной . (Каноническая система называется моногенной, если из любой строки можно создать не более одной новой строки за один шаг, т. е. система детерминирована.)

Системы переписывания строк, формальные грамматики типа 0

Система переписывания строк — это особый тип канонической системы Поста с одним начальным словом, и каждая продукция имеет форму

${\displaystyle P_{1}gP_{2}\ \rightarrow \ P_{1}hP_{2}}$

То есть каждое продукционное правило представляет собой простое правило замены, часто записываемое в форме g → h . Доказано, что любая каноническая система Поста сводима к такой системе подстановки , которая, как формальная грамматика , также называется грамматикой фразовой структуры , или грамматикой типа 0 в иерархии Хомского .

Рекомендации

• Эмиль Пост , «Формальные сокращения общей проблемы комбинаторного решения», Американский журнал математики 65 (2): 197–215, 1943.
• Марвин Мински , Вычисления: конечные и бесконечные машины , Prentice-Hall, Inc., Нью-Джерси, 1967.