1. Введение
Влияние подпрограмм (англ. subroutine) на программирование без преувеличения огромно. Введенные на заре программирования они не теряют своей актуальности и поныне. Без них практическое программирование представить просто невозможно. Хотя с формальной точки зрения они не так уж и нужны, т.к. чистую теорию интересуют больше свойства алгоритма, чем его размеры.
В теории автоматов понятие вложенных автоматов, на базе которых строилась бы практика автоматных подпрограмм (АПП), обсуждается редко. Подобная (вложенная) иерархическая организация автоматов, если и рассматривается, то весьма поверхностно. Одной из причин подобного отношения может служить сложность реализации вложенной иерархии на аппаратном уровне [1, 2].
Программирование более гибко и предоставляет больше возможностей, чем практика проектирования цифровых схем. В этом нам предстоит убедиться, рассматривая далее программную реализацию вложенных автоматов, а следом и концепцию автоматных рекурсивных алгоритмов.
При всех частных проблемах формирования вложенной автоматной модели ее формальное определение не вызывает каких-то проблем. Но, с другой стороны, выбор построения иерархии модели, безусловно, будет оказывать существенное влияние на ее программную реализацию.
Читать полностью »