Постканоническая система
-
Определение и свойства постканонических систем
- Постканоническая система — это система, которая преобразует строки, используя конечные правила.
- Каждая постканоническая система может быть представлена как система перезаписи строк.
- Формальные языки, генерируемые постканоническими системами, являются рекурсивно перечислимыми.
-
Теорема о нормальной форме
- Система находится в нормальной форме, если у нее есть только одно начальное слово и простые производственные правила.
- Пост доказал теорему о нормальной форме для постканонических систем в 1943 году.
-
Системы перезаписи строк
- Система перезаписи строк — это постканоническая система с одним начальным словом и простыми правилами подстановки.
- Любая постканоническая система может быть сведена к системе перезаписи строк.
Полный текст статьи: