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

[DoubleNCH]

Если задана диаграмма переходов конечного автомата, то как построить схему его реализующую ?

[arseniiv]

Схему из логических элементов, что ли? А в чём трудности? Пронумеруйте состояния, представьте эти числа наборами битов, входной алфавит (и выходной, если автомат что-то выдаёт) тоже в двоичные наборы отобразите. И…

[DoubleNCH]

http://i.imgur.com/t3ieYbl.png
Я составил таблицу, нашёл канонические уравнения, теперь осталось построить схему...

[arseniiv]

Схемы по формулам можно по-всякому составлять. Например, найти их КНФ — дальше прозрачно, какие элементы откуда пойдут.

[DoubleNCH]

А где об этом можно почитать ? Я не могу понять что делать...
Я получил следующие канонические уравнения:
$y(t)=x_1(t) \oplus x_2(t) \oplus q(t)$
$q(t+1)=x_1(t)x_2(t) \oplus x_1(t)q(t) \oplus x_2(t)q(t)$

[arseniiv]

Алгоритм широко известен:

arseniiv в сообщении #640056 писал(а):

1) Выражаете все операции кроме конъюнкции, дизъюнкции и отрицания через эти три.
2) Привести формулу к виду с отрицаниями только перед переменными, но не другими подформулами.
3) Пользуясь дистрибутивностью, довести формулу до КНФ или ДНФ.

Кстати, а вдруг вам разрешено использовать xor-элементы?

[DoubleNCH]

Разрешено.
Так я и получил вначале СДНФ, а потом упростил до данного выражения.

[arseniiv]

Тогда не читайте про КНФ, хотя это могло бы пригодиться в других случаях.

Попробуйте сначала нарисовать схему по уравнению $z = ab\mathbin{\rm xor}c$.

-- Чт мар 13, 2014 19:43:18 --

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

Так я и получил вначале СДНФ, а потом упростил до данного выражения.

В общем, уже не важно. Раз трудности состоят в переводе формул в схему.

-- Чт мар 13, 2014 19:44:12 --

(Оффтоп)

(Какой я молодец, перепутал КНФ и ДНФ…)

[DoubleNCH]

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

[arseniiv]

Почему было не начать с вопроса о задержках?

Можно сначала рассмотреть $q(t+1)$ как никак не связанное с $q(t)$. Это уже потом сигнал с данного выхода можно провести через элемент задержки на вход.

-- Чт мар 13, 2014 19:51:38 --

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

Знаю что в треугольники мы записываем функциональные элементы, вершины - это наши аргументы, будет и выход.

Строите схемы сначала для простых формул типа $ab, a\vee b$, потом на основе этих схем получаете схемы для более сложных формул. Больше никаких тайн.

[DoubleNCH]

arseniiv в сообщении #836392 писал(а):

Можно сначала рассмотреть $q(t+1)$ как никак не связанное с $q(t)$.

Оно у меня связанно.
$y(t)=x_1(t) \oplus x_2(t) \oplus q(t)$
$q(t+1)=x_1(t)x_2(t) \oplus x_1(t)q(t) \oplus x_2(t)q(t)$

[Deggial]

DoubleNCH, формулы оформляйте $\TeX$ом, а программный код - тегом code, в противном случае тема переедет в места не столь отдалённые.

[arseniiv]

arseniiv в сообщении #836392 писал(а):

Строите схемы сначала для простых формул типа $ab, a\vee b$, потом на основе этих схем получаете схемы для более сложных формул. Больше никаких тайн.

Или так: представьте, что вам надо вычислить значение формулы, но вместо значений 0 и 1 и булевых функций оказались входные сигналы и логические элементы.

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

Оно у меня связанно.
$y(t)=x_1(t) \mathbin{\rm xor} x_2(t) \mathbin{\rm xor} q(t);$
$q(t+1)=x_1(t)x_2(t) \mathbin{\rm xor} x_1(t)q(t) \mathbin{\rm xor} x_2(t)q(t).$

Всё равно $q(0)$ надо будет откуда-то брать в реализации. Так что представьте, что на входе вместе с другими есть и $q(t)$.

[DoubleNCH]

Ну вот я получил моё основное уравнение $y(t)=x_1(t) \oplus x_2(t) \oplus q(t)$.
Да я нарисую две вершины $x_1$ и $x_2$ и треугольник со знаком xor. Опущу две стрелки в этот треугольник и на выходе будет одна стрелка. Это схема $ x_1(t) \oplus x_2(t) $. А что делать с $ q(t) $ куда его... ? Не понимаю

P.S. Можно я всё это переделаю через часика два, просто я не знаком с ТEX...постараюсь прочитать и исправлю в срок.

[arseniiv]

Кстати, примеров схем вам не показывали? От этого зависит, стоит ли вообще как-то обозначать связь значений $q$ от разных моментов времени.

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

Ну вот я получил моё основное уравнение $y(t)=x_1(t) \mathbin{\rm xor} x_2(t) \mathbin{\rm xor} q(t)$.
Да я нарисую две вершины $x_1$ и $x_2$ и треугольник с знаком xor. Опущу две стрелки в этот треугольник и на выходе будет одна стрелка. Это схема $x_1(t) \mathbin{\rm xor} x_2(t)$. А что делать с q(t) куда его... ? Не понимаю

Может, расставить скобки в уравнении?

Конкретные вопросы — это замечательные вопросы!