Выходное слово - последовательность выходных сигналов, выдаваемых автоматом. Состояния автомата - это комбинации состояний запоминающих элементов устройства.

Однако даже с прикладной точки зрения интерпретация автомата как устройства не является универсальной. Известно, что всякое вычислительное устройство можно реализовать как аппаратно (в виде устройства), так и программно (в виде программы для ЭВМ). Это приводит к более общему истолкованию автоматов как алгоритмов с конечной памятью, многие свойства которых можно исследовать безотносительно к способу их реализации.

Программная реализация логических функций и автоматов.

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

Под программой будем понимать пронумерованную последовательность команд k_{1, …} , k_s, взятых из некоторого фиксированного набора (системы команд). Программа работает над конечным множеством пронумерованных (или поименованных ) двоичных ячеек. Номер (или имя ) ячейки называ­ется ее адресом ; именем ячейки часто будет служить имя логической пе­ременной, значения которой хранятся в этой ячейке.

Система команд содержит команды-операторы вида b:=f(a_{1, …} , a_p) (выполнить операцию над содержимым ячеек a_{1, …} , a_p и результат поло­жить в ячейку b ) и двухадресные условные переходы двух видов: 1) “если а, то i, иначе j ”( если a = 1, то перейти к выполнению команды k_ί , иначе перейти к k_j ) ; 2 ) ” если ā ( a = 0 ) , то i , иначе j ”. Операция f ( a₁ , . . . , a_p ) - это логическая функция p переменных ; в частности, она может быть константой 0 или 1. Если j - номер следующей команды, то переход можно считать одноадресным : ” если a, то i, ( иначе перейти к следую­щей команде ) ”, а если i = j, то безусловным : ” перейти к i “. Любая из команд указанных типов может быть заключительной, что указывается сло­вом ” конец “.

Процессом вычисления программы k₁, . . . , k_s называется после­довательность шагов k ( 1 ), k ( 2 ), . . . , k ( t ), на каждом из которых вы­полняется одна команда программы. Эта последовательность определяется так : 1) k ( 1 ) = k₁; 2) если k (1) = k_r - оператор, то k ( i + 1 ) = k_r+1 ; 3) если k ( 1 ) - условный переход, то номер команды k ( i + 1 ) указывается этим переходом; 4) если k ( i ) - заключительная команда, то процесс вычисления останавливается после ее выполнения. Число t называется вре­менем ее выполнения.

Программа П вычисляет (или реализует ) логическую функцию f ( х₁ , . . . , х_n ) = у, если для любого двоичного набора σ = ( σ₁ , . . . , σ_n ) при на­чальном состоянии памяти х₁ = σ₁ , х₂ = σ₂, . . . , х_n = σ_n (состояние ос­тальных ячеек несущественно ) программа через конечное число шагов ос­танавливается и при этом в ячейке у лежит величина f ( σ₁ , . . . , σ_n).

Если под сложностью схемы, реализующий автомат, обычно понимается число элементов в схеме, то сложность программы можно понимать в различных смыслах: 1) число команд в тексте программы; 2) объем промежуточной памяти, т.е. число ячеек для хранения промежуточных результатов вычислений; 3) время вычисления, которое будет характеризоваться двумя величинами: средним временем t_ср (П) =1/2ⁿ åτ_р(σ) и максимальным временем t_макс(П) = max_s τ_р(σ), где сумма и максимум бе­рутся по всем 2ⁿ двоичным набором σ, а τ_р - время работы программы П на наборе σ.

Любой схеме, реализующей функцию f и содержащей N элементов, не­трудно поставить в соответствие программу, реализующую f и состоящую из N команд, следующим образом. Занумеруем элементы схемы числами 1,2, . . . , n так, чтобы на любом пути от входа к выходу номера элемен­тов возрастали; при этом номер 1 получит один из входных элементов, а номер N - выходной элемент. Пусть элемент е_ί схемы реализует функцию φ_ί и к его входам присоединены выходы элементов е_j1, . . . , е_jp ( некоторые из них, возможно, являются входами схемы). Поставим элементу е_ί в соот­ветствие либо ячейку а_ί и команду а_ί = φ_ί ( а_j1 , . . . , а_jp ), если ί ≠ N; либо ячейку у и команду << у : = φN( а_j1, . . . , а_jp ) конец >>, если ί = N. Полу­чим программу, не содержащую условных переходов ( такие программы будем называть операторными ), в которой порядок команд в точности со­ответствует нумерации элементов в схеме, а система команд – базису схемы.

Проблемы синтеза операторных программ в основном сводятся к про­блемам синтеза схем: в частности вопросы функциональной полноты сис­темы команд и минимизации собственного текста операторной программы совпадают соответственно с задачами функциональной полноты системы функций и о минимизации схем. Поскольку операторная программа не содержит условных переходов, время ее вычисления на любом наборе одно и то же. Отсюда t_max = t_cp = N, то есть оба вида временной сложности совпадают со сложностью текста программы, и, следовательно, при доста­точно больших n почти для всех функций близки к 2ⁿ ⁄ n. Наоборот, про­блема минимизации памяти ( за счет многократного использования одной ячейки для нескольких промежуточных результатов ) для операторных про­грамм является нетривиальной комбинаторной задачей.

Другой ”крайний “ вид программ, вычисляющих логические функции, - программы, состоящие из команд вида у : = σ ( σ = 1 или σ = 0 ) и услов­ных переходов. Такие программы называются бинарными программами. Всякую булеву функцию F , содержащую N букв, можно реализовать би­нарной программой, вычисляющей F за время t_max = N и содержащей N команд условных переходов ( а также две команды у = 1 и у = 0, которые в оценках не участвуют ). Для описания метода реализации используем представление программы в виде графа в котором вершины соответствуют командам, а ребра – переходам. Пусть G₁ - граф программы для функций f₁ с начальной вершиной v₁₀ и двумя заключительными вершинами v_1z⁰ ( с командой у = 0 ) и v_1z¹ ( с командой у = 1 ) ; G₂ - граф программы для f₂ с началом v₂₀ и концами v_2z⁰ и v _2z¹. Тогда: 1) программа, граф G которой получен присоединением G ₂ к ”нулю“ G ₁ ( то есть отождествлением вер­шин v _1z⁰ и v ₂₀¹ ; команда у : = 1 при этом отбрасывается, вычисляют функ­цию f = f ₁ / f ₂; 2) программа, граф G которой получен присоединением G ₂ к ”единице“ G ₁ ( отождествляем v _1z¹ и v₂₀ ), вычисляет f = f ₁ &f ₂; 3) программа, граф которой получен из G ₁ заменой команд в v _1z⁰ и v _1z¹ на инверсные, вычисляет f ₁. Заметим, что в графе G - две нулевые заклю­чительные вершины. Их необходимо отождествлять.