Теория Автоматов (2)

[DoubleNCH]

Конечный автомат задан схемой. Построить диаграмму переходов, систему канонических уравнений и таблицу.
Второе задание на рисунке:


-- 13.03.2014, 21:12 --

Вот для первого треугольника думаю так:
$x(t) \oplus x(t+1)$
А далее ?

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: просьба вставить рисунок удобнее

DoubleNCH
Вставьте рисунок нормально:
1) Уберите всю лишнюю информацию с картинки - зачем она?
2) Оформите рисунок в тег img, чтобы юзеры $n$ раз не лазили на отдельную страничку.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
прелестно

[arseniiv]

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

Вот для первого треугольника думаю так:
$x(t) \oplus x(t+1)$

Кстати, сначала хорошо бы определиться, в какой момент времени подан икс на вход. Если он подан в $t+1$, то выражение правильное, а если в $t$, то будет $x(t-1)\oplus x(t)$. Если вы не против, давайте рассматривать время $t$.

Второму треугольнику его выход подаётся на вход с задержкой. Т. к. выход — $y(t)$, на вход подастся $y(t-1)$. Что подастся на другой вход, вы нашли: $x(t-1)\oplus x(t)$. Значит, $y(t) = (x(t-1)\oplus x(t))\oplus y(t-1)$.

Теперь стоит это уравнение преобразовать в систему вида

$$\begin{array}{l} y(t) = \ldots(x(t),q(t)), \\ q(t+1) = \ldots(x(t),q(t)). \end{array}$$

[DoubleNCH]

Пусть будет $t$ :)
А почему будет именно $t-1$. От слово задержать сигнал на одну итерацию ? Или что ? Второй треугольник ясен. Сейчас попробую привести к виду.

[arseniiv]

Ага. Один икс приходит в то же время, а другой придёт потом, т. е. в данный момент приходит старый — бывший в $t-1$.

[DoubleNCH]

arseniiv
что-то я не пойму как преобразовать данное уравнение ...

[arseniiv]

Кстати, я не совсем хорошо написал. Заранее ведь неизвестно, не больше ли двух состояний у автомата. Если так, придётся три уравнения выдумывать, и для $q_1$, и для $q_2$, или ещё больше, хотя тут это уже вряд ли.

А ещё, если так подумать, не обязательно преобразовывать уравнения. Можно попытаться перебрать все варианты работы вручную…

[DoubleNCH]

Можно пожалуйста подробнее ? Вот что нам нужно сделать имея в активе лишь полученное уравнение: $y(t) = (x(t-1)\oplus x(t))\oplus y(t-1)$.

[arseniiv]

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

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

что-то я не пойму как преобразовать данное уравнение ...

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

[DoubleNCH]

А как тогда быть. Вот такое вот задание на семинаре. Вроде не должно быть сложным. Дана схема конечного автомата.

[arseniiv]

Просто немного покрутить формулу туда-сюда. Можно представить, что конечные уравнения уже есть, и выразить их них $y(t+1)$, потом сравнить с тем, что есть.

[DoubleNCH]

А как мне узнать сколько тут состояний ?

[arseniiv]

Хороший вопрос. Надеюсь, кто-нибудь придёт и скажет, как попроще. Интуитивно кажется, что число состояний не больше $2^\text{количество элементов задержки}$, но не считал.

Кстати, а что с литературой по этой области? Должна же быть. Я просто читал немного другое, связь автоматов с регулярными выражениями и пр., а «схематической» реализации касался только раз. Странно, что нет ответов других участников.

[DoubleNCH]

Литературы нет вообще...Я уж не знаю.
Вот можно было сделать вот так вот. Глядя на схемы мы видим два функциональных блока, вот и положим что состояний тоже два. Пусть $x(t)=q_1(t+1)$, тогда для первого треугольника получим $x(t) \oplus q_1(t)$. Пусть на выходе второго треугольника будет $q_2(t+1)$. Тогда для второго треугольника а значит и для всей системы получим $x(t) \oplus q_1(t) \oplus q_2(t)$.
Имеем:
$\begin{cases} y(t)=x(t) \oplus q_1(t) \oplus q_2(t)\\ q_1(t+1)=x(t)\\ q_2(t+1)=x(t) \oplus q_1(t) \oplus q_2(t)\end{cases}$

[arseniiv]

Если два состояния, хватит одной $q$ — она же может принимать два значения, 0 и 1.