Краткая версия статьи опубликована в журнале "Мир ПК", 2002. №2, C.144-149.
Более полная версия статьи доступна на сайте журнала "Мир ПК" (www.pcworld.ru).
(краткая аннотация)
(C) 2001 г. А.А.Шалыто, Н.И.Туккель
Федеральный научно-производственный центр
ГУП "НПО "Аврора"",
Санкт-Петербургский государственный институт точной механики и оптики
(технический университет)
Отсюда можно скачать полный текст статьи в формате pdf (225 кб)
Настоящая работа посвящена преобразованию классической модели машины Тьюринга в другую модель, обеспечивающую переход от тьюрингова программирования к автоматному. Последнее весьма эффективно для систем со сложным поведением, характерным для задач управления или сводимым к ним, что демонстрируется на классических задачах распознавания цепочек для:
Первые два языка, задаваемые контекстно-свободными грамматиками, требуют использования модели автомата с магазинной памятью, а для третьего языка, определяемого контекстно-зависимой грамматикой, необходим переход к линейно-ограниченным автоматам.
В настоящей работе показано, что при использовании предлагаемого подхода, изменение типа грамматики не приводит к необходимости использования модели другого типа, а вызывает лишь незначительное усложнение графа переходов.
Отмечено, что если Дж. фон Нейман изменил машину Тьюринга для эффективной аппаратной реализации алгоритмов (например, введением арифметическо-логического устройства), то в настоящей работе делается аналогичная попытка преобразования этой машины с целью повышения эффективности программирования. При этом, если в машине Тьюринга автомат решает две задачи (управление и вычисление, не свойственное для него), то в предлагаемом подходе он решает только задачу управления, а вычисления осуществляются в объектах управления, предназначенных для этой цели (например, регистры, счетчики и т.д.).