Теория автоматов. Рациональные отношения.

[Xaositect]

Профессор Снэйп в сообщении #292801 писал(а):

Что касается ответа на исходный вопрос темы, то он, очевидно, положительный. Трансдьюсер строится элементарно. Кроме вникания в определение трансдьюсера и задаваемого им отношения для решения задачи ничего не нужно.

Ну это да, основная проблема в том, чтобы представить трансдьюсер в том виде, в котором его вводил конкретный преподаватель

[Профессор Снэйп]

Xaositect в сообщении #292796 писал(а):

2) Если $U$ и $V$ — множества из $\mathcal{R}$, то множества $U\cup V$ и $U\cdot V = \{u\cdot v|u\in U, v\in V\}$ (произведение) также принадлежат $\mathcal{R}$;

Произведение --- это, видимо, конкатенация. По крайней мере, точно не пересечение

-- Сб фев 27, 2010 01:31:50 --

Xaositect в сообщении #292803 писал(а):

Ну это да, основная проблема в том, чтобы представить трансдьюсер в том виде, в котором его вводил конкретный преподаватель

А это топегстартер сам должен сделать. Мы ведь тут готовые решения не выкладываем! (Только по прошествии двух лет )

-- Сб фев 27, 2010 01:37:54 --

Указания к построению нужного трансдьюсера.

К примеру, для $k=1$ (для остальных аналогично). Остаёмся в стартовом состоянии до тех пор, пока идёт точное соответствие между буквами. Стартовое состояние не конечное. Как только идёт расхождение, переходим в другое, конечное состояние и остаёмся в нём при всех точных соответствиях. Любое следующее расхождение между буквами уводит нас из этого конечного состояния в "тупиковое" неконечное.

Этим обеспечивается корректная работа трансдьюсера, когда вход и выход одинаковой длины. Если они разной длины, надо делать недетерминированное предположение о том, какое из двух слов длиннее и уводить трансдьесер в одно из двух соответствующих "тупиковых" неконечных состояний.

Получается (недетерминированный?) трансдьюсер с пятью состояниями.

[pincher]

Спасибо

[Профессор Снэйп]

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