Каноническая система сообщений

редактировать

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

Содержание

1 Определение
- 1.1 Пример (правильно сформированные скобочные выражения)
2 Теорема о нормальной форме
3 Системы переписывания строк, формальные грамматики нулевого типа
4 Ссылки

Определение

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

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

↓ h 0 $ 1 ′ h 1 $ 2 ′ h 2… $ n ′ hng 10 $ 11 г 11 $ 12 г 12… $ 1 м 1 г 1 м 1 г 20 $ 21 г 21 $ 22 г 22… $ 2 m 2 g 2 m 2 ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ gk 0 $ k 1 gk 1 $ k 2 gk 2… $ kmkgkmk {\ 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}}}}

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

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

g 0 $ 1 g 1 $ 2 g 2… $ mgm → h 0 $ 1 ′ h 1 $ 2 ′ час 2… $ n ′ hn {\ 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}}

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)...

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

A Постканоническая система называется нормальной, если она имеет только одно начальное слово и каждое производственное правило имеет простую форму

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

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

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

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

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

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

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

P 1 g P 2 → P 1 h P 2 {\ displaystyle P_ {1} gP_ {2} \ \ rightarrow \ P_ {1} hP_ {2}}

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

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

Ссылки

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