Построить конечный детерминированный автомат, минимизировать его, записать канонические уравнения. $$y(t)=x(t) \vee \overline{x(t-1)} $$ $$t\geqslant 2, y(1)=1$$ Прошу помощи, вообще не могу понять тему. Даже не могу написать что у меня получилось, ибо не получилось ничего. Заранее благодарен.

  1. Я так понимаю, что нужно заполнить таблицу переходов-выходов и нарисовать диаграмму Мура,минимизировать и далее построить каноническую таблицу и по ней составить систему канонических уравнений. x(t),y(t)∈ B, B={0,1}
  2. http://hkar.ru/mcqi http://hkar.ru/mcqh http://hkar.ru/mcqg http://hkar.ru/mcqd http://hkar.ru/mcqc http://hkar.ru/mcqb http://hkar.ru/mcqa http://hkar.ru/mcq9 http://hkar.ru/mcq2 http://hkar.ru/mcq1 http://hkar.ru/mcq0 http://hkar.ru/mcpZ http://hkar.ru/mcpY
  3. Огромное спасибо за то, что столько со мной возитесь. Пожалуйста напишите более подробно.
  4. http://hkar.ru/meCb вот что вышло.

задан 22 Ноя '13 8:26

изменен 23 Ноя '13 7:58

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

(22 Ноя '13 8:31) falcao

@Alek: я ставил вопрос о той форме представления данных, которая берётся за основу в том курсе, который Вам читается. Дело в том, что автоматы можно задавать очень многими способами -- в том числе таблицами и чем угодно. Можно просто нарисовать картинку, можно сделать что-то ещё. Если Вы дадите ссылку на текст, где с самого начала изложена суть всех используемых здесь условных обозначений, то будет шанс ответить на Ваш вопрос.

(22 Ноя '13 10:19) falcao

Добавлю к сказанному выше, что мне непонятен содержательный смысл используемых здесь обозначений $%x(t)$% и $%y(t)$%. Этими буквами в принципе можно обозначить что угодно. Есть какие-то общие соглашения типа того, что $%q(t)$% -- это состояние в момент $%t$%, а всё остальное может обозначаться по-разному.

(22 Ноя '13 10:42) falcao

Теперь всё стало предельно ясно. Вам нужен автомат, реализующий функцию. Именно этих двух слов мне не хватало для понимания того, что требуется сделать. В этом случае всё просто: автомат запоминает предыдущий входной символ, что осуществляется через выбор состояния. Всего состояний будет три: начальное $%q_0$%, а также состояния $%q_1$%, $%q_2$%. Автомат переходит в $%q_1$%, если была введена единица, и в $%q_2$%, если введён ноль. То, что должно быть на выходе, теперь легко вычисляется по формулам из условия. Если этих кратких замечаний мало, то ближе к вечеру могу написать подробнее.

(22 Ноя '13 12:04) falcao
10|600 символов нужно символов осталось
0

Вот более подробное объяснение.

Функция $%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

10|600 символов нужно символов осталось
0

Мне понравилась эта методичка. Можете выложить?

ссылка

отвечен 13 Ноя '14 2:07

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×965

задан
22 Ноя '13 8:26

показан
2795 раз

обновлен
13 Ноя '14 9:17

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru