|
Построить конечный детерминированный автомат, минимизировать его, записать канонические уравнения. $$y(t)=x(t) \vee \overline{x(t-1)} $$ $$t\geqslant 2, y(1)=1$$ Прошу помощи, вообще не могу понять тему. Даже не могу написать что у меня получилось, ибо не получилось ничего. Заранее благодарен.
задан 22 Ноя '13 8:26 
Alek |
|
Вот более подробное объяснение. Функция $%y(t)$%, которую надо реализовать в виде вычисляющего её автомата, принимает значения $%y(t)=x(t)\vee1=1$% при $%x(t-1)=0$% и $%y(t)=x(t)\vee0=x(t)$% при $%x(t-1)=1$%. Чтобы в памяти автомата сохранилась информация о том, чему было равно предыдущее поданное на вход значение, введём состояния $%q_1$% и $%q_2$% помимо начального состояния $%q_0$%. Нахождение автомата в состоянии $%q_1$% будет означать, что перед этим на вход подавалось $%1$%, а нахождении в состоянии $%q_2$% -- что на вход подавалось $%0$%. Такой автомат легко нарисовать: из вершины $%q_0$% идёт стрелка с меткой $%1/1$% в $%q_1$% и стрелка с меткой $%0/1$% в $%q_2$%. Внизу пишется $%1$% по причине того, что $%y(1)=1$%. Далее исследуем вершину $%q_1$%. Здесь мы находимся в ситуации, соответствующей $%x(t-1)=1$%, поэтому выходной символ совпадает с входным. Рисуем стрелку $%0/0$%, направляя её в $%q_2$% и стрелку $%1/1$%, направленную в $%q_1$%, то есть в себя. Для вершины $%q_2$% мы имеем случай $%x(t-1)=0$%, и здесь выходной символ всегда равен $%1$%. Рисуем стрелку с меткой $%0/1$%, идущую в $%q_2$% и стрелку $%1/1$% в $%q_1$%. Построение автомата завершено, и теперь легко заметить, что его можно минимизировать, так как из $%q_0$% выходят стрелки с теми же метками и того же назначения, как из $%q_2$%. Это позволяет отождествить $%q_0$% и $%q_2$%. Осуществляется это так: стираем $%q_0$% вместе с выходящими из неё стрелками, а вершину $%q_2$% переименовываем в $%q_0$% (она считается начальной). Этот автомат уже минимален, так как одним состоянием здесь заведомо не обойтись. отвечен 22 Ноя '13 20:33 
falcao |
Здесь надо сначала прояснить смысл используемых обозначений. У Вас в лекционных записях или в методическом руководстве должно быть описание того, как строится автомат по этим данным. То есть надо знать, что берётся в качестве множеств вершин (состояний), какие там имеются переходы и так далее. Само по себе понятие автомата может вводиться по-разному в разных источниках, поэтому надо уточнить используемый язык.
@Alek: я ставил вопрос о той форме представления данных, которая берётся за основу в том курсе, который Вам читается. Дело в том, что автоматы можно задавать очень многими способами -- в том числе таблицами и чем угодно. Можно просто нарисовать картинку, можно сделать что-то ещё. Если Вы дадите ссылку на текст, где с самого начала изложена суть всех используемых здесь условных обозначений, то будет шанс ответить на Ваш вопрос.
Добавлю к сказанному выше, что мне непонятен содержательный смысл используемых здесь обозначений $%x(t)$% и $%y(t)$%. Этими буквами в принципе можно обозначить что угодно. Есть какие-то общие соглашения типа того, что $%q(t)$% -- это состояние в момент $%t$%, а всё остальное может обозначаться по-разному.
Теперь всё стало предельно ясно. Вам нужен автомат, реализующий функцию. Именно этих двух слов мне не хватало для понимания того, что требуется сделать. В этом случае всё просто: автомат запоминает предыдущий входной символ, что осуществляется через выбор состояния. Всего состояний будет три: начальное $%q_0$%, а также состояния $%q_1$%, $%q_2$%. Автомат переходит в $%q_1$%, если была введена единица, и в $%q_2$%, если введён ноль. То, что должно быть на выходе, теперь легко вычисляется по формулам из условия. Если этих кратких замечаний мало, то ближе к вечеру могу написать подробнее.