Показать, что L = {WW^R: W ∈ Σ *} не является регулярным использованием Насосной Лемма

Question

Если я позволяю строка w быть a^mb^m то мы знаем, что y будет состоять только из a-х из-за правилами |xy| <= m.

И если я установил i=0, то ww^R будет иметь меньше a с левой стороны, чем с правой стороны. Таким образом, это доказывает, что этот язык не является регулярным.

Однако мой текст книги (Введение формальных языков и автоматных стр. 118 по Linz) говорит, что если бы мне пришлось выбирать w = a^2m и пусть y = aa, то я бы неудачу.

Но как это сделать?

На мой взгляд, независимо от того, что x, y, z, тем первый a^2m будет меньше a «с или больше, в зависимости от того, что i является чем второй a^2m.

Answer 1

Причина, по которой у вас есть ровный скаляр на m. Так как строки в L - это просто обратная строка, добавленная к себе, четное число a 's всегда будет находиться в L.

Для любого м> = 1 у вас есть аа аа [...]. Итак, когда ваш оппонент выбирает y = aa, они заставляют вас вводить строку, которая находится в L в w (i). Независимо от того, сколько раз, если вообще, это закачивается вы в конечном итоге с: (аа)^к: к = насосы, который является строкой в ​​L

Я думаю, что это плохой выбор для использования только a. Наличие двух символов алфавита обычно облегчает победу. Поскольку книга продолжает говорить, вы не можете предположить, что ее легко опередить; любые попытки автоматически недействительны.