Формальные языки, нужна помощь

[lightcaster]

Добрый день, помогите пожалуйста c такой вот проблемкой из теории формальных языков.

Two words x and y are conjugate if xz = zy for some word z. Show that this
equation holds if and only if x = uv, y = vu, z = $(uv)^ku$ for some words u, v and k ≥ 0.

Чувствую, что нужно использовать индукцию по |xz|, но как именно - не понимаю.
Спасибо.

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

Лучше индукцию по $|z|$.

Ясно, что для любого $i$ от $1$ до $\min \{ |x|, |z| \}$ $i$-ая буква слова $x$ совпадает с $i$-ой буквой слова $z$. Значит, возможны 2 случая.

1) $x = zw$ для некоторого слова $w$. Получаем $xz = zwz = zy$, $y = wz$, $u = z$, $v = w$ и $k = 0$.

2) $z = xw$ для некоторого слова $w$. Получаем $xz = xxw = zy = xwy$ и $xw = wy$ с $w$ более коротким, чем $z$.

P. S. Случай $|x| = 0$ рассматриваем отдельно. В этом случае $y = x$ и утверждение, которое просят доказать, вообще неверно

[lightcaster]

Спасиб большое! Идею понял.
Я рассматривал те же два варианта, но на варианте 1 запнулся: не понял как использовать индуктивную гипотезу, когда ее тут использовать и не нужно.

А что касается случая |x|=0, почему условие не выполняется? Мы же можем взять u=0,v=0 и k=0 (т.е. строки нулевой длины).

ps не посоветуете хорошую книжку по формальным доказательствам (в т.ч. где рассматривалась бы мат. индукция)?

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

lightcaster в сообщении #343970 писал(а):

А что касается случая |x|=0, почему условие не выполняется? Мы же можем взять u=0,v=0 и k=0 (т.е. строки нулевой длины).

Можно. Но можно взять и по другому! Вы просите доказать, что при равенстве $xz = zy$ всегда найдутся $u$ и $v$, однако при пустых $x$, $y$ и не пустом $z$ такие $u$ и $v$ не найдутся.

[lightcaster]

Да, вы правы. Спасибо за помощь.