1.4. Конечность алфавита

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

Множество значений, которые переменная v может принимать, называется алфавитом переменной v и обозначается через элемент v алфавита V называется символом. Пусть — конечные множества с соответствующими элементами и пусть множество обозначает множество всех упорядоченных -значных наборов . Если входные переменные данной системы суть , то входной алфавит этой системы, обозначаемый через X, определяется выражением

где — алфавит

Аналогично, если выходные переменные системы суть то выходной алфавит Z системы определяется выражением

где — алфавит

Если X имеет мощность мощность , то мощности для X и q для Z выразятся соответственно формулами:

Мощности и q конечны.

Из определения входного алфавита X видно, что одного символа входного алфавита — входного символа — достаточно для описания всех и входных переменных в любой Заданный момент времени . Аналогично из определения выходного алфавита Z видно, что одного символа выходного алфавита — выходного символа — достаточно для описания всех w выходных переменных в любой заданный момент времени Следовательно, входные переменные могут быть заменены одной входной переменной алфавит которой X определяется выражением (1.1). Выходные переменные могут быть заменены одной выходной переменной z, алфавит которой Z определяется выражением (1.2). Соответственно и входных клемм можно заменить одной входной клеммой и w выходных клемм — одной выходной клеммой. В результате получим схематичное изображение, имеющее вид двухклеммного ящика (рис. 1.3), которое является стандартным представлением основной модели конечного автомата.

Рис. 1.3. Представление конечного автомата в виде «черного ящика».

Для иллюстрации рассмотрим вычислительное устройство, которое имеет две входные линии по линии подаются символы 0 и 1, по линии — символы 1, 2 и 3. В произвольные моменты времени устройство выдает величины . Таким образом, имеем:

и, следовательно,