Задачки

[_Swetlana]

Эх, все верхние и нижние индексы слетели.
Поэтому скажу просто. ДМТ - как филолог  У неё на входе входное слово, а на выходе - выходное слово.

А лекцию я залила на яндекс-диск
https://disk.yandex.ru/i/huau-CQcdMwfvA

[_Swetlana]

Вот эти ДМТ обе подходят под вашу задачу, т.к. при любых входных сигналах выдают последовательностей нулей. А вот структурные схемы у них разные.

[Andrey Lukyanov]

Во-первых, неправильно посчитали

В чём неправильно? Это теоретический максимум.

Во-вторых, забыли условие При некоторых входных сигналах есть переход из любого состояния в другое. (или для любого состояния найдется сигнал, который это состояние сменит)

Эти значит лишь, что часть вариантов надо отсеять.

[Andrey Lukyanov]

На входе 2 бита (входной сигнал и внутреннее состояние) и на выходе 2 бита (выходной сигнал и новое внутреннее состояние). Всего 4⁴=64 разных варианта устройства чёрного ящика.

Ошибочка вышла. 4⁴=256.

[Agnius]

Вот эти ДМТ обе подходят под вашу задачу, т.к. при любых входных сигналах выдают последовательностей нулей. А вот структурные схемы у них разные.

Я же уже писал

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

Эти значит лишь, что часть вариантов надо отсеять.

Ну так отсейте 

[Andrey Lukyanov]

Ну так отсейте 

Если, например, рассмотреть те варианты, у которые выходное внутреннее состояние никогда не меняется (всегда 1 или всегда 2), то их 32 штуки. Тогда из 256 остаётся 224.

[Andrey Lukyanov]

Ещё надо учесть те варианты, где можно перейти из 1 в 2, но нельзя из 2 в 1 (или наоборот).

Если я ничего не путаю, то всего вариантов с «неполноценными» переходами между внутренними состояниями должно получиться 128-32=96.

То есть из 256 вариантов остаётся уже 160.

[_Swetlana]

Я же уже писал

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

Я не понимаю ваших шмелизмов 
Ни у ДМТ, ни у её состояний нет алгоритмов, ДМТ сама алгоритм.
У ДМТ есть функция переходов. Выше я прикрепила лекцию. Откройте, прочитайте и пользуйтесь общепринятой терминологией.
У двух ДМТ на моём рисунке функции переходов разные. Всё. Что нужно сделать в вашей задаче - совершенно непонятно.

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

[yurifromspb]

По-моему, у Агния автомат Мили, а не ДМТ. ДМТ ведь пишет на ту же ленту, может ездить кареткой влево-вправо, и лента дана вся сразу (хотя, конечно, можно и менять, но это надо оговорить). Там ещё символы для незаписанной области есть.
ИМХО, задачу надо понимать так:
Надо найти такую входную последовательность, по которой за конечное время можно определить (предьявить алгоритм определения) класс эквивалентности автомата Мили с двумя состояниями, двумя входными символами и двумя выходными символами. Эквивалентными надо считать (при некоторых предположениях об осмысленности условия) такие автоматы, которые для любых одинаковых входов дают одинаковые выводы. Иными словами, если автоматы задают одинаковые функции на {0,1}*->{0,1}*, то они эквивалентны.
Плюс дано ограничение на функцию переходов - из любого состояния всегда можно выйти.

[yurifromspb]

Стартовое состояние тоже имеет значение.

[Andrey Lukyanov]

Попробую ещё поупражняться в подсчёте вариантов.

Всего отображений из исходных 2 бит в бит нового внутреннего состояния — 16. Перебором можно определить, что только 9 из них обеспечивают отсутствие застревания в одном из состояний. Поскольку у нас есть ещё 16 разных отображений из исходных 2 бит в бит выходного сигнала, то получается 9×16=144 разных варианта устройства чёрного ящика.



Если ещё предъявить требование, чтобы выходной сигнал всегда можно было бы установить как в 0, так и в 1, то у нас останется 14 разных отображений на выходной бит (исключаются «всегда 0» и «всегда 1»). Тогда получится 9×14=126 разных вариантов устройства чёрного ящика.

[_Swetlana]

По-моему, у Агния автомат Мили, а не ДМТ. 

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

и лента дана вся сразу (хотя, конечно, можно и менять, но это надо оговорить).

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

[_Swetlana]

Стартовое состояние тоже имеет значение.

Стартовое состояние всегда q1 

[_Swetlana]

Эквивалентными надо считать (при некоторых предположениях об осмысленности условия) такие автоматы, которые для любых одинаковых входов дают одинаковые выводы. Иными словами, если автоматы задают одинаковые функции на {0,1}*->{0,1}*, то они эквивалентны.
Плюс дано ограничение на функцию переходов - из любого состояния всегда можно выйти.

Там должно быть отображение (изоморфизм же) мн-ва состояний одного автомата на мн-во состояний другого... Неохота вспоминать всю эту автоматную муть 

[Agnius]

Поскольку у нас есть ещё 16 разных отображений из исходных 2 бит в бит выходного сигнала, то получается 9×16=144 разных варианта устройства чёрного ящика.

А вот это уже верно 

Если для вас приведенные на рисунке выше ДМТ (по вашему внутреннему убеждению) изоморфны, то ваше убеждение к задаче не пришьёшь. Вы должны корректно сформулировать определение изоморфизма двух ДМТ. Дв

Да я уже привел, это множество всех автоматов, которые имеют одинаковые функции дачи выходных символов для каждого состояния, а значит, переходы между состояниями могут быть любыми
yurifromspb
Все абсолютно верно 

Ну и изоморфизм у автоматов как-то стандартно определяется, неохота вспоминать как

Да, я знаю, о каком изоморфизме вы говорите, он более узкий, чем озвученный выше функциональный (т.е. два автомата могут быть не изоморфны, но иметь одинаковую внешнюю функцию выдачи выходной строки в зависимости от входной) И в данном простом случае нет нетривиальных изоморфизмов (в общепринятом смысле)

Неохота вспоминать всю эту автоматную муть

Так это же как вроде ваша специальность, думал уж вы то решите 

[_Swetlana]

Так это же как вроде ваша специальность, думал уж вы то решите 

Это была тема моего диплома, 2022-1982, ровно 40 лет тому назад. Больше я никогда этой автоматной мути не касалась. Неудачно выбрала руководителя диплома, потом неудобно было менять. 

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