Мне бы очень понравилась ваша помощь в этом решении о том, является ли язык всех слов над алфавитом {0,1}, который не может быть прочитан с обеих сторон одинаковым образом, { w | w <> wR } - это контекстно-свободный язык (который является, оно может быть преобразовано в конкретные грамматические правила).
Я попытался доказать, что он не является контекстно-свободным языком по лемме перекачки, но я не нашел строку, которая приведет меня к противоречию.
Любые предложения?
Если я правильно читаю ваш вопрос, вы хотите посмотреть, не является ли набор непалиндромов свободным от контекста языком.
Это свободный от контекста язык:
S --> 0S0 | 1S1 | R
R --> 0V1 | 1V0
V --> 0V0 | 1V1 | R | 1 | 0 | ε
Начиная с S, идея состоит в том, чтобы построить строку извне. S позволяет разместить столько совпадающих или нулей, сколько вы хотите (возможно, нет), пока не достигнете случая R, в котором есть не -совпадение. Оттуда вы можете поместить либо совпадения, либо не-совпадения (потому что на этом этапе мы уже гарантированно не будем палиндром). Этого достаточно, чтобы описать все непалиндромы - извне внутрь, они начинаются с нуля или больше совпадающих пар, затем одна несогласованная пара, а затем ноль или более пар (совпадение или нет). Наконец, в середине может быть или не быть символ.
P.S. Если у вас его еще нет, книга Сипсера "Теория вычислений", несомненно, превосходна. На самом деле, это единственная книга колледжа, которую я все еще читаю время от времени.
Этот вопрос, по общему признанию, стоит у меня в голове как компьютерный ученый. Но, как математик, у меня есть кое-что, чтобы внести свой вклад здесь.
Если w сам по себе является контекстно-свободным языком, существует закрытие для реверсии w:
Контекстно-свободные языки закрываются при следующих операциях. Что если
LиPявляются контекстно-свободными языками, то следующие языки: контекстно-свободный:...
- обращение L
Кажется, это все, что задают здесь. Эти ссылки содержат дополнительную справочную информацию о том, как производятся исходные и последующие закрытые формы.
(Дополнительная, потенциально полезная ссылка из теории множеств)