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

1.5. Состояния

В то время как в качестве входов и выходов выбираются такие переменные, которые исследователь может наблюдать и измерять, природа промежуточных переменных часто может оставаться неизвестной, а измерение их — невозможным. Значение промежуточных переменных, однако, заключается не в характере изменения каждой из них, а скорее в их комбинированном действии на зависимости между входными и выходными переменными. Это комбинированное действие, так же как и переменные, вызывающие его, подчинено предположениям о дискретности времени и конечности алфавита, введенным в §§ 1.3 и 1.4. Указанное действие называется состоянием системы. Состояние системы в момент будем обозначать через . Набор всех возможных состояний системы, которые ей присущи, называется множеством состояний и обозначается через 5.

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

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

определить выходной символ в данный тактовый момент и состояние в следующий тактовый момент.

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

появление двух цифр, появление первого герба), где «появление первой цифры» - состояние системы, когда цифра выпала первый раз после герба, «появление двух цифр» — состояние системы, когда цифра выпала после цифры, и «появление первого герба» — состояние системы, когда герб выпал после герба или после цифры. Отметка производится каждый раз, когда система находится в состоянии «появление двух цифр» и входом является цифра или когда система находится в состоянии, отличном от состояния «появление первого герба», и входом является герб. Если состояние в настоящий момент — «появление первой цифры» или «появление двух цифр», то состояние в следующий момент будет «появление двух цифр», если входом является цифра, и «появление первого герба», если входом является герб. Если состояние в настоящий момент — «появление первого герба», то состояние в следующий момент будет «появление первой цифры», если входом является цифра, и «появление первого герба», если входом является герб. Таким образом, подтверждается, что выбранное множество состояний отвечает предъявляемым требованиям, так как по известному состоянию системы и входу в настоящий момент может быть определен выход в настоящий момент и состояние в следующий.

Выбор множества состояний в общем случае является сложной задачей, которая решается не обязательно однозначно. Так как не существует общих правил для выбора множества состояний, то часто прибегают к методу последовательного приближения путем проб и ошибок. Затраты времени на выбор состояний и их число, вообще говоря, зависят от интуиции и степени знания исследуемой системы.

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