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