WikiDer > Постканоническая система - Википедия

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

Определение

А Постканоническая система является тройкой (А,я,р), куда

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

${ 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 }}}}$

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

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

${ 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}}$

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

Пример (выражения в квадратных скобках)

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

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

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

${ Displaystyle г $ rightarrow $ h}$

После 1943 г. Теорема о нормальной форме, который применяется к наиболее общему типу канонической системы Post:

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

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

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

А система перезаписи строк - это особый тип канонической системы Post с одним начальным словом, и каждая продукция имеет вид

${ Displaystyle P_ {1} gP_ {2} rightarrow P_ {1} hP_ {2}}$

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

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

• Эмиль Пост, "Формальные редукции общей комбинаторной задачи о решениях", Американский журнал математики 65 (2): 197-215, 1943.
• Марвин Мински, Вычисления: конечные и бесконечные машины, Прентис-Холл, Инк., Нью-Джерси, 1967.