Теория абстрактных автоматов

[Ramil987]

Задача.
Покажите, что для отображений $z$ и $h$,
заданных равенствами $z(p)=pp$ (удвоение слова $p$); $h(p) = p'$ , $p'$ где получено из $p$ изъятием всех вхождений некоторой буквы входного алфавита, существует более экономная процедура выравнивания длины слов, чем стандартное выравнивание длины слов?

Попытка решения:
Для этого мы можем использовать следующую процедуру:
Пусть $w_1$ и $w_2$ - слова из языков $L_1$ и $L_2$ соответственно.
Применим отображение $h$ к каждому слову, чтобы получить новые слова $h(w_1)$
и $h(w_2)$ . Вычислим длину максимального общего префикса $p$ между $h(w_1)$ и $h(w_2)$ . Затем мы можем использовать отображение $z$ для удвоения префикса $p$ и получения новых слов $z^{|p|}(h(w_1))$ . и $z^{|p|}(h(w_2))$. После этого мы можем сравнить длины новых слов и выбрать то, которое короче. Эта процедура экономнее, чем стандартное выравнивание длины слов, потому что она не требует добавления дополнительных символов в конец слов, что может привести к увеличению размера языка. Вместо этого она использует отображения $h$ и$z$ , чтобы
выровнять длины слов без добавления дополнительных символов.