Лингвофорум

Цитата: Agnius от февраля 13, 2022, 21:16
Так это же как вроде ваша специальность, думал уж вы то решите 

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

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

Цитата: Andrey Lukyanov от февраля 13, 2022, 17:57
Поскольку у нас есть ещё 16 разных отображений из исходных 2 бит в бит выходного сигнала, то получается 9×16=144 разных варианта устройства чёрного ящика.

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

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

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

Цитата: _Swetlana от февраля 13, 2022, 20:26
Ну и изоморфизм у автоматов как-то стандартно определяется, неохота вспоминать как

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

Цитата: _Swetlana от февраля 13, 2022, 20:31
Неохота вспоминать всю эту автоматную муть

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

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

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

Цитата: yurifromspb от февраля 13, 2022, 17:45
Стартовое состояние тоже имеет значение.

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

Цитата: yurifromspb от февраля 13, 2022, 17:32
По-моему, у Агния автомат Мили, а не ДМТ. 

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

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

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

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

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

---

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

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

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

Цитата: Agnius от февраля 13, 2022, 14:32
Я же уже писал

Цитата: Agnius от февраля 11, 2022, 22:36
Тут можно уточнить - если алгоритмы для обоих состояний одинаковы, то нам не важна динамика переходов между внутренними состояниями.

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

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

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

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

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