язык L = {xy |x, y в {a, b} *, | x |= | y |} это точно язык слов четной длины:
Каждое слово четной длины находится в L: если w в {a, b} * четное, то существуетнекоторое натуральное число k такое, что | w |= 2 * к. Следовательно, w можно разбить на два слова длины k, поэтому в {a, b} * есть x, y, такие что w = xy и | x |= | y |= к. Следовательно, w находится в L.
Каждое слово в L имеет четную длину: рассмотрим w в L. Тогда по определению L существуют x, y в {a, b}* такой, что | x |= | y |и ш = ху. Следовательно, | w |= | xy |= | х |+ | y |= 2 * | x |. Следовательно, w имеет четную длину.
Далее, вы должны показать, что L является регулярным. Вы можете сделать это, построив DFA с двумя состояниями q0 и q1, где q0 - начальное состояние, а также принимающий. С q0 чтение a или b возвращает вас к q1, а с q1 чтение a или b возвращает вас к q0. Тогда слова, для которых пробег автомата заканчивается в q0, являются в точности словами четной длины.