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

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

Определение [ править ]

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

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

{\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$ — заданное фиксированное слово, а каждый $ и $’ — переменная , обозначающая произвольное слово. правила Строки до и после стрелки в производственном правиле называются антецедентами и консеквенциями соответственно. Требуется, чтобы каждый $' в консеквенте был одним из $ в антецедентах этого правила и чтобы каждый антецедент и консеквент содержали хотя бы одну переменную.

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

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)  $ ₁ $ ₂ →  $ ₁ []  $ ₂

  Образование нескольких слов в языке правильно построенных скобочных выражений: 

         [] начальное слово 
         [][] по (2) 
         [[][]] по (1) 
         [[][]][[][]] по (2) 
         [[][]][][[][]] по (3) 
         ...

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

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

g\$\ \rightarrow \ \$h

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

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

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

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

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

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

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

Ссылки [ править ]

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