Отношение конгруэнции на языках

[NiGHTeR]

ПомогиТе с задачей:

На алфавите $\Sigma$ задано отношение $x\sim y \leftrightarrow \ \forall u,v \in \Sigma^{*} uxv\in L \leftrightarrow uyv\in L$. Как доказать, что классы эквивалентности этого отношения образуют моноид? То есть для любых двух классов $[x], [y] \rightarrow [x][y]=[xy]$.

[NiGHTeR]

$[x][y]=\{x_{i}y_{j}: x_{i}\sim x; y_{i}\sim y\}$. Обозначим, $w\Leftrightarrow t$ если w и t одновременно принадлежат или не принадлежат L.

Рассмотрим произвольное слово $w=x_{i}y_{j} \in [x][y]$. Тогда, $\forall u,v \in \Sigma^{*} \ ux_{i}y_{j}v\Rightarrow uxy_{j}v\Rightarrow uxyv$. => $[x][y]\subseteq {[xy]}$

[bnovikov]

NiGHTeR в сообщении #511121 писал(а):

$[x][y]=\{x_{i}y_{j}: x_{i}\sim x; y_{i}\sim y\}$. Обозначим, $w\Leftrightarrow t$ если w и t одновременно принадлежат или не принадлежат L.

Рассмотрим произвольное слово $w=x_{i}y_{j} \in [x][y]$. Тогда, $\forall u,v \in \Sigma^{*} \ ux_{i}y_{j}v\Rightarrow uxy_{j}v\Rightarrow uxyv$. => $[x][y]\subseteq {[xy]}$

Ну, теперь доказывайте обратное включение: $[x][y]\supseteq {[xy]}$, а затем - ассоциативность.

[NiGHTeR]

Ассоциативность следует из ассоциативности конкатенации. А вот как обратное включение доказать - не знаю.

[bnovikov]

NiGHTeR в сообщении #511134 писал(а):

Ассоциативность следует из ассоциативности конкатенации. А вот как обратное включение доказать - не знаю.

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

Вы ввели эквивалентность $\sim$, нужно доказать, что это конгруэнция. После этого определяется умножение $[x][y]=[xy]$ на классах, и здесь уже ничего доказывать не нужно.

[NiGHTeR]

Во как! А у нас дали определение, что данное отношение конгруэнтность, и сказали доказать, что фактор по нему-моноид

А что такое конгруэнтность?

[bnovikov]

Где Вы учитесь и на каком курсе? (Спрашиваю для того, чтобы доступно объяснить) По какому учебнику учитесь?

[NiGHTeR]

Мфти, 2 курс, предмет - теория реализации языков программирования, учебника нет-нам семинарист лично методички рассылает, щас - тема синтаксический моноид

[bnovikov]

NiGHTeR в сообщении #511206 писал(а):

Мфти, 2 курс, предмет - теория реализации языков программирования, учебника нет-нам семинарист лично методички рассылает, щас - тема синтаксический моноид

Сочувствую. Итак, начали. Есть конгруэнция $\sim$, т.е. из $x\sim y$ следует $xz\sim yz$ и $zx\sim zy$ для любого $z.$ Как я писал, определяем умножение классов $[x][y]=[xy]$. Теперь основное - нужно проверить, что это умножение определено корректно. Это означает, что если Вы берете произведение классов $[x']$ и $[y']$, то оно должно равняться $[xy]$ (поскольку $[x']=[x]$ и $[y']=[y]$). Таким образом, Вам нужно доказать, что если $x\sim x'$ и $y\sim y'$, то $xy\sim x'y'$. Вот и пробуйте доказать!

[NiGHTeR]

А разве корректно об умножения не проверяется как равенство множеств [x] и [y]?

-- Вс дек 04, 2011 17:23:34 --

А из того что $x\sim y;\ x'\sim y' \Rightarrow xx'\sim yy'$ следует только что $[x][y]\subseteq [xy]$ ?

[bnovikov]

NiGHTeR в сообщении #511378 писал(а):

А разве корректно об умножения не проверяется как равенство множеств [x] и [y]?

-- Вс дек 04, 2011 17:23:34 --

А из того что $x\sim y;\ x'\sim y' \Rightarrow xx'\sim yy'$ следует только что $[x][y]\subseteq [xy]$ ?

Да, и бОльшего не надо. Смотрите на $[x],[y],[xy]$ как на элементы множества классов (на котором определяется операция), а не как на множества.

Вообще, полезно полистать некоторые книжки, например:
Лаллеман_Полугруппы и комбинаторные приложения
Брауэр_Введение в теорию конечных автоматов

[NiGHTeR]

То есть мы просто ввели операцию $[x]\circ [y]=[xy]$?

[bnovikov]

NiGHTeR в сообщении #511397 писал(а):

То есть мы просто ввели операцию $[x]\circ [y]=[xy]$?

Совершенно верно.

[NiGHTeR]

А тогда верно ли что эта операция будет совпадать с операцией конкатенации соответствщих множеств?

[bnovikov]

NiGHTeR в сообщении #511423 писал(а):

А тогда верно ли что эта операция будет совпадать с операцией конкатенации соответствщих множеств?

Как мы с Вами уже выяснили, нет. Включение, вообще говоря, верно только в одну сторону.