Задачка на регулярность языков

[NiGHTeR]

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

Дан регулярный язык $X$. В том же алфавите задан язык $Y$, состоящий из всех таких слов что $XY=YX$. (т.е. является наибольшим множеством, коммутирующим с X) Является ли язык $Y$ регулярным?

[NiGHTeR]

У меня такое ощущение, что максимальным коммутирующим с языком $X$ будет язык $Y=X^{*}$. Верно ли это?

[Joker_vD]

Я не въезжаю, что тут означает коммутируемость. То есть вот беру я слово $x\in X$, беру слово $y\in Y$, составляю $xy \in XY$, и оно... что? Должно принадлежать $YX$? Т.е. $xy=y'x'$?

[NiGHTeR]

Равенство множеств $XY=YX$ где $XY=\{w_{1}w_{2}: w_{1}\in X; w_{2}\in Y \}$ - конкатенация языков

-- Пн сен 26, 2011 22:07:05 --

Joker_vD в сообщении #486664 писал(а):

Я не въезжаю, что тут означает коммутируемость. То есть вот беру я слово $x\in X$, беру слово $y\in Y$, составляю $xy \in XY$, и оно... что? Должно принадлежать $YX$? Т.е. $xy=y'x'$?

ну как то так) только мы заведомо не знаем что есть $Y$

[bnovikov]

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

Равенство множеств $XY=YX$ где $XY=\{w_{1}w_{2}: w_{1}\in X; w_{2}\in Y \}$ - конкатенация языков

Напишите правильное условие задачи. Если $XY=YX$ понимать так, как Вы написали, то может не существовать наибольшего $Y$.

[NiGHTeR]

ну $Y$ это подмножество алфавита $\Sigma^{*}$ поэтому наибольший существует (по включению).

А точное условие: в алфавите $\Sigma$ дан регулярный язык $X$. Рассматривается наибольшее множество $Y$ - множество всех элементов (в том же алфавите)для которых верно: $XY=YX$ (операция - конкатенация языков). Будет ли язык $Y$ регулярным?

-- Вт сен 27, 2011 00:19:46 --

и лично моя гипотеза, будет ли верным, что $Y=X^{*}$

[bnovikov]

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

ну $Y$ это подмножество алфавита $\Sigma^{*}$ поэтому наибольший существует (по включению).

А точное условие: в алфавите $\Sigma$ дан регулярный язык $X$. Рассматривается наибольшее множество $Y$ - множество всех элементов (в том же алфавите)для которых верно: $XY=YX$ (операция - конкатенация языков). Будет ли язык $Y$ регулярным?

Опять неграмотно!
"поэтому наибольший существует (по включению)" - ???

"множество всех элементов (в том же алфавите)для которых верно: $XY=YX$" - бессмысленно. Если Вы считаете, что $Y$ - это элемент, тогда другое дело. Но из контекста видно, что это не так.

[NiGHTeR]

почему не верно то?

$X=\{a, aa\}; Y=\{a\}^{*}; XY=YX=\{a\}^{*}$

-- Вт сен 27, 2011 02:59:13 --

а наибольший будет существовать, потому что $Y\in\Sigma^{*}$

[bnovikov]

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

почему не верно то?
$X=\{a, aa\}; Y=\{a\}^{*}; XY=YX=\{a\}^{*}$

Это верно.

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

а наибольший будет существовать, потому что $Y\in\Sigma^{*}$

Я пытаюсь выбить из Вас правильную формулировку, но это не получается. Еще раз: фраза "множество всех элементов (в том же алфавите), для которых верно $XY=YX$ " бессмысленна, потому что про элемент этого множества нельзя сказать: " это элемент, для которого верно $XY=YX$".

Ну, да Бог с Вами. Начинать надо вот с чего. Рассматриваем множество языков (а не элементов) $Y$, для которых верно $XY=YX$. Объединение таких языков снова обладает этим свойством, поэтому, действительно, существует наибольший среди них. Обозначим его через $Z$. Вы спрашиваете, верно ли, что $Z=X^*$? Ответ: нет. Пример: $X=\{abab\}$. Тогда $ab\cdot abab=abab\cdot ab$, но $ab\not\in X^*$.

[NiGHTeR]

Цитата:

Я пытаюсь выбить из Вас правильную формулировку, но это не получается. Еще раз: фраза "множество всех элементов (в том же алфавите), для которых верно $XY=YX$ " бессмысленна, потому что про элемент этого множества нельзя сказать: " это элемент, для которого верно $XY=YX$ ".

да, но ведь для заданного языка $X$ и элемента $y$ можно проверить что $Xy=yX$ а дальше мы все такие элементы $y\in \Sigma^{*}$ (для которых это выполняется) помещаем в множество $Y$.

2) Ну да, глупость сказал. По крайней мере $X^{*}$ входит в $Z$.

я вообще не знаю как к этой задаче подступиться.

-- Вт сен 27, 2011 14:02:46 --

Еще можно заметить, если $\varepsilon\in X$ то $X^{*}\Sigma^{*} X^{*} \subseteq Z$

[bnovikov]

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

да, но ведь для заданного языка $X$ и элемента $y$ можно проверить что $Xy=yX$ а дальше мы все такие элементы $y\in \Sigma^{*}$ (для которых это выполняется) помещаем в множество $Y$.

Опять непонятно. $XY=YX$ ($Y$ - язык) и $(\forall y\in Y) Xy=yX$ - это разные условия! Так скажите, наконец, какое из них Вам дано?

[NiGHTeR]

дано первое, что $XY=YX$

[bnovikov]

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

дано первое, что $XY=YX$

Тогда начинать надо примерно так:

Возьмем некоторый $y\in Y$. Тогда для любого $x\in X$ найдутся такие $x'\in X, y'\in Y$, что $yx=x'y'$. Поэтому либо $y=x's$, либо $ys\in X$ для некоторого $s\in \Sigma^*$. Как дальше - не знаю, пробуйте сами. Посмотрите, как в свободной полугруппе решается уравнение $xy=yx$, это может натолкнуть на мысль. Возможно, поможет лемма о накачке или что-то похожее.