Автоматные языки и их классификация

Автоматным языком считается такая совокупность, с помощью которой явно описывается автомат. К таким средствам относятся таблицы (Т), матрицы (М) и графы (Г).

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

• ТП - таблица переходов;
• ТВ - таблица выходов;
• СТП и В - совмещенная таблица переходов и выходов;
• ОТП - отмеченная таблица переходов;
• МП - матрица переходов;
• МВ - матрица выходов;
• СМП и В - совмещенная матрица переходов и выходов;
• ОМП - отмеченная матрица переходов.

Из рисунка следует, что для ЦА Мили и Мура могут использоваться и одинаковые средства (ТП, ТВ, МП), и разные средства (СТП и В и ОТП; СМП и В и ОМП). Пунктирно обведенные средства использовать можно, но нецелесообразно. Зачеркнутое средство МВ является невозможным.

Данный материал является фрагментом из: Триханов А.В. Теория автоматов: Учебное пособие
©  Томский политехнический университет, 1999