Главная > Методы обработки данных > Введение в теорию конечных автоматов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

1.9. Другая модель

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

Таблица 1.1. Функции для системы рис. 1.4 (см. скан)

переменной как упорядоченной пары . Алфавит S переменной s, следовательно, определяется выражением

Используя уравнение (1.5), представим в виде

Из определения s и уравнения (1.6) получаем выражение для :

Уравнения (1.21) и (1.23) определяют вторую модель конечного автомата, в которой состояние однозначно определяет

выходной сигнал). Если мощность входного алфавита системы равна p, а мощность множества состояний равна n, то мощность S будет

Система, соответствующая второй модели, определяемая уравнениями (1.21) и (1.23), может быть всегда представлена основной моделью, определяемой уравнениями вида (1.5) и (1.6), входящими в определение 1.1.

Это можно сделать, положив Тогда из равенства (1.21) получим:

Из определения и уравнения (1.23) получаем:

Нетрудно видеть, что уравнения (1.24) и (1.25) выражают характеристические функции основной модели конечного автомата.

Так как любая система, представимая одной моделью, представима также другой моделью и так как множество требуемых состояний для второй модели часто значительно больше, чем для основной модели, то использование второй модели не имеет каких-либо преимуществ. Поэтому в книге мы будем воздерживаться от использования второй модели, и когда будут делаться ссылки на характеристические функции конечного автомата, то следует иметь в виду функции, определяемые уравнениями (1.5) и (1.6).

<< Предыдущий параграф Следующий параграф >>
Оглавление