Способы задания автоматов

Для задания автоматов существуют специальные формализованные языки.

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

К начальным языкам относятся: язык регулярных выражений, язык предикатных форм, язык логических схем алгоритма. Широкого применения эти языки не нашли. Для описания частного класса автомата оказался удобным начальный язык логических схем алгоритмов НЯЛСА.

Если рассматривать автомат с учетом его внутренних состояний, то необходимо определить функции перехода (из внутреннего состояния x_i во внутреннее состояние x_j не исключая i=j). Задание функций выходов означает, что каждой паре поставлено в соответствие состояние выхода .

Языки позволяющие таким образом описать автомат называются стандартными языками. К стандартным относятся таблицы переходов, таблицы выходов, матрицы переходов, таблицы включений, графы переходов.