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

[DoubleNCH]

Я не знаю вообще ничего... блин...сделали вот так вот ) Как теперь построить диаграмму перехода так это ещё сложнее. я запутался вообщем.

[arseniiv]

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

$\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}$

Хороший подход! Теперь можно попробовать свести $q_1$ и $q_2$ к одной $q$, вдруг возможно. Но даже если и нет, с потенциальными четырьмя состояниями можно построить диаграмму. И по ней станет понятно, не продублировались ли нечайно состояния.

Номер состояния — $q_1 + 2q_2$ (или наоборот. И вообще можно как угодно, лишь бы удобно было). Теперь можете узнать, в каком состоянии автомат на какие входы даёт какие выходы, ну и куда переходит — вот она, схема. Сразу из уравнений.

[DoubleNCH]

Цитата:

с потенциальными четырьмя состояниями

а почему четыре, у меня ж два ?

[arseniiv]

Вот такую таблицу заполните:

$$\begin{array}{|c|c||c|c|} \hline q(t) & x(t) & y(t) & q(t+1) \\ \hline 00 & 0 & ? & ?? \\ 00 & 1 & ? & ?? \\ 01 & 0 & ? & ?? \\ \cdots & \cdots & \cdots & \cdots \\ 11 & 1 & ? & ?? \\ \hline \end{array}$$

Чтобы не считать в голове и не ошибиться случайно при рисовании диаграммы переходов.

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

а почему четыре, у меня ж два ?

У $q_1$ два состояния, у $q_2$ два. Всего четыре!

[DoubleNCH]

а разве $q$ ни есть само состояние ?

[arseniiv]

$(q_1,q_2)$ — состояние. Ведь автомат один, состояние тоже одно, а этих штук две, и в общем случае не известно, зависят ли их значения друг от друга. (Но после это можно выяснить.)

[DoubleNCH]

$$\begin{array}{|c|c||c|c|} \hline q(t) & x(t) & y(t) & q(t+1) \\ \hline 00 & 0 & 0 & 00 \\ 00 & 1 & 1 & 11\\ 01 & 0 & 1 & 01\\ 01 & 1 & 0 & 10\\ 10 & 0 & 1 & 01 \\ 10 & 1 & 0 & 10 \\ 11 & 0 & 0 & 00 \\ 11 & 1 & 1 & 11 \\ \hline \end{array}$$

[arseniiv]

О. Правда, что-то тут не так (см. ниже).

Есть алгоритм упрощения КА, я его точно не помню, но, судя по всему, этот автомат эквивалентен автомату с двумя состояниями вот с такой таблицей:

$$\begin{array}{|c|c||c|c|} \hline q(t) & x(t) & y(t) & q(t+1) \\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ \hline \end{array}$$

Заметно, что пары состояний (00 и 11) и (01 и 10) были эквивалентными, вот и объединяем их. Если вы строили диаграмму переходов, тоже могли заметить, как они похожи.

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

Про «что-то тут не так»: этот автомат никогда не меняет состояние. В каком он оказался вначале, в том и будет работать всё время — обычно подразумевается, что состояние хоть раз должно поменяться на каком-то наборе входных символов. Это наводит на мысль, что таблица, или уравнения, к ней приведшие, или и то, и то не соответствуют схеме. Увы, у меня уже поздно, и не могу проверить.