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

[pincher]

$\rho (u,v)$ - расстояние Хэмминга между словами одинаковый длины. $k \in \mathbb{N}.$ Является ли отношение $\alpha \subseteq A^* \times A^*$ рациональным, если
$u\alpha v \Longleftrightarrow \rho (u,v) = k?$

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

[Xaositect]

как связаны рациональные отношения с двухленточными автоматами?

[pincher]

Я не знаю что такое двухленточный автомат, у нас не было такого термина.
Такие задачи задачи у нас на зачете по теории автоматов, отсюда и название темы.

Отношение задает некоторое подмножество. А рациональное множество можно рассматривать как рационалный язык. По теореме Клини, если множество является рациональным, то оно распознается некоторым конечным автоматом. Мне кажется что решением задачи будет либо автомат распознающий язый либо доказательство того что такого автомата не существует.

Только я не уверен, что написанное выше верно.

[Xaositect]

Именно так все и обстоит. Нужно построить автомат или доказать, что его нет.

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

У нас, видимо, непонятки с терминологией. Вы по какому учебнику занимаетесь? Терминология для меня незнакомая, словосочетание "рациональное отношение" меня вывело только на книгу Брауэра по автоматам. А там есть теорема о том, что рациональные отношения есть в точности множества, принимаемые двухленточными ЭМ-автоматами.

[pincher]

Учебников у нас не было, преподаватель сам давал материал.

А определение рационального отношения, следующее.
Это подмножество образованное конечным числом операций $A\cup B A\cap B$ и $A$*

Иногда его еще называют регулярным на сколько я знаю.

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

Термин "рациональное отношение" я тоже впервые слышу.

-- Сб фев 27, 2010 00:47:38 --

В Вики есть: http://en.wikipedia.org/wiki/Finite_state_transducer

Цитата:

The class of relations computed by finite state transducers is known as the class of rational relations.

[Xaositect]

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

Бр-рр. Регулярный --- это объединение, конкатенация и звёздочка. А тут объединение, пересечение и звёздочка. Всё-таки немного другое... Возможно, "регулярный язык" и "рациональный язык" --- разные вещи.

У Брауэра объединение, конкатенация и звездочка.

А еще у него определение рационального отношения есть, почти такое же, но для пар слов, т.е. по сути рассматривается не моноид $A^{*}$ слов в алфавите $A$, а моноид $A^{*}\times B^{*}$, а определение то же.

[pincher]

в данном случае пересечение = конкатенация. Я наверное неточно выразился.

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

В Вики в указанной выше статье конкатенация вообще не определяется. Определяются объединение, пересечение, звёздочка и композиция.

К сожалению, никогда не имел дела с трансдьюсерами, ничего о них не знаю

[Xaositect]

А теорема о том, что регулярные языки есть в точности те, что принимаются конечными автоматами, была?

А что-нибудь было в теории именно о рациональных отношениях, т.е. о подмножествах $X^{*}\times X^{*}$?

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

pincher в сообщении #292777 писал(а):

в данном случае пересечение = конкатенация. Я наверное неточно выразился.

Да нет, это всё-таки разные вещи. Если ориентироваться на статью в Вики, пересечение есть пересечение, конкатенацией там и не пахнет. Скорее конкатенация = композиция.

-- Сб фев 27, 2010 00:59:26 --

Упс... Проглядел с ходу, есть там конкатенация. И пересечение тоже есть, это разные вещи!

Цитата:

Concatenation. Given transducers T and S, there exists a transducer such that if and only if w[T]y and x[S]z.
...
Intersection. Given transducers T, S, the intersection of these transducers H has the property that (1) x[H]y if and only if x[T]y and x[S]y.

Половина символов в цитате не отобразилась

[Xaositect]

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

Если ориентироваться на статью в Вики, пересечение есть пересечение, конкатенацией там и не пахнет.

Указанная статья писал(а):

Concatenation. Given transducers $T$ and $S$, there exists a transducer $T\cdot S$ such that $wx[T\cdot S]yz$ if and only if $w[T]y$ and $x[S]z$.

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

Да я нашёл уже. Просто звёздочка и пересечение синие, а конкатенация чёрная и её сразу не видно

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

-- Сб фев 27, 2010 01:09:00 --

В немецкой Вики написано "регулярные отношения"

http://de.wikipedia.org/wiki/Transduktor_(Informatik)

Видать, правда синонимы

[Xaositect]

Цитата из Брауэра:

Определение 8.4.9. Множество $Rat(X, Y)$ рациональных подмножеств произведения $F(X)\times F(Y)$ есть наименьшее подмножество $\mathcal{R}$ булеана $\mathcal{B}(F(X)\times F(Y))$, обладающее следующими свойствами:
1) $\varnothing\in\mathcal{R}$, $\{(x, \Lambda)\}\in\mathcal{R}$ и $\{(\Lambda, y)\}\in\mathcal{R}$ для всех $x\in X$ и $y\in Y$;
2) Если $U$ и $V$ — множества из $\mathcal{R}$, то множества $U\cup V$ и $U\cdot V = \{u\cdot v|u\in U, v\in V\}$ (произведение) также принадлежат $\mathcal{R}$;
3) Если $U\in \mathcal{R}$, то $\mathcal{R}$ содержит также и порожденный множеством $U$ подмоноид $U^{*}$ моноида $(F(X)\times F(Y), \cdot)$, т. е. множество $U^{*} = U^0\cup U^1\cup U^2\cup\dots$.

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

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