Теория Автоматов

[DoubleNCH]

Построить схему, реализующую инициальный конечный автомат, распознающий наличие во входной последовательности подслов одного из видов: 00, 011 и, выдающий на выходе 1 в точности в те моменты, когда на входе появляется последняя буква одного из этих подслов.

Я понимаю как можно построить схемы конечного автомата заданного каноническими уравнениями. Но не могу понять как построить схему тут...

[nikvic]

Для начала нарисуйте автомат с 7-ю состояниями, который помнит 2 последние буквы.

[DoubleNCH]

nikvic
я не знаю как такой построить.

[nikvic]

Назовите их "пусто", "нолик", "единичка", ... "пара палок" и расставьте стрелочки

[DoubleNCH]

nikvic
мне всё это сложно даётся. Ничего не понимаю. Как можно вообще схемой реализовать это. Вот еслиб у меня было уравнение $y(t)=$... то я б построил, а так не пойму.

[svv]

Хорошо. Просто расставьте стрелочки. Скопируйте эту картинку в Paint и добавьте стрелочки. Из каждого кружка-состояния должны выходить две стрелочки:
одна (синяя) показывает, в какое состояние перейдет автомат, если на вход поступит $0$, другая (красная) показывает, в какое состояние перейдет автомат, если на вход поступит $1$.

[DoubleNCH]

svv
это вы мне сейчас предлагаете построить диаграмму перехода. Ну зачем ?

[svv]

Я не настаиваю.

[DoubleNCH]

svv
да я и не против. Но меня это с толку сбивает. я не могу всё это связать.

[arseniiv]

Вообще-то для этой задачи тоже есть вполне ясный алгоритм (и, вроде, не один). Неужели опять с литературой плохо? Странный у вас курс какой-то. (Я бы сказал, где его можно найти, но не помню. )

[DoubleNCH]

arseniiv
ну дали там две книги Кудрявцев В.Б., Алёшин С.В., Подколзин А.С.-Введение в теорию автоматов и Кудрявцев В.Б., Алёшин С.В., Подколзин А.С.-Элементы теории автоматов. Теория вроде как ясна. Но там не особо много уделяется построению схем, диаграмм. Практика совершенно иное... Я уже отчаялся.

[iifat]

DoubleNCH в сообщении #839003 писал(а):

Я понимаю как можно построить схемы конечного автомата заданного каноническими уравнениями

Канонические — это регулярными выражениями? Ну, можно попробовать написать регулярное выражение.

[DoubleNCH]

iifat, вот такой системой:
$\[\left\{ \begin{array}{l} y(t) = \psi (q(t),a(t))\\ q(t + 1) = \varphi (q(t),a(t))\\ q(0) = q \end{array} \right.\]$