Является {ш |w <> w ^ R} над алфавитом {0,1} неконтекстный язык? - PullRequest
Новая
       39

Является {ш |w <> w ^ R} над алфавитом {0,1} неконтекстный язык?

12 голосов
/ 27 марта 2012

Мне бы очень хотелось, чтобы вы помогли решить, является ли язык всех слов в алфавите {0,1}, который не может быть прочитан с обеих сторон одинаковым образом, { w | w <> w<sup>R</sup> }, контекстно-свободным языком (что это может быть преобразовано в определенные правила грамматики).

Я пытался доказать, что это не контекстно-зависимый язык, используя лемму прокачки, но я не нашел строку, которая приведет меня к противоречию.

Есть предложения?

Ответы [ 2 ]

11 голосов
/ 05 апреля 2012

Если я правильно читаю ваш вопрос, вы посмотрите, не является ли набор непалиндромов языком без контекста.

Это язык без контекста: 

S --> 0S0 | 1S1 | R
R --> 0V1 | 1V0
V --> 0V0 | 1V1 | R | 1 | 0 | ε

Начиная с S, идея состоит в том, чтобы построить строку снаружи в. S позволяет вам разместить столько совпадающих единиц или нулей, сколько вы хотите (возможно, ни одного), пока не достигнете случая R, в котором есть не -матч. Оттуда вы можете размещать совпадения или несоответствия (потому что на этом этапе мы уже гарантированно не являемся палиндромом). Этого достаточно, чтобы описать все непалиндромов - снаружи внутрь , они начинаются с нуля или более совпадающих пар, затем с одной несовпадающей парой, а затем с нуля или более пар (совпадающих или нет). Наконец, в середине может быть или не быть символ.

P.S. Если у вас его еще нет, книга Сипсера по теории вычислений, несомненно, превосходна. Фактически, это единственная книга о колледже, которую я до сих пор читаю.

2 голосов
/ 05 апреля 2012

Этот вопрос, по общему признанию, стоит у меня над головой как ученый. Но, как математик , я могу внести свой вклад.

Если w сам по себе является контекстно-свободным языком, существует замыкание для решения сторнирования w:

Контекстные языки закрыты для следующих операций. Тот если L и P являются контекстно-свободными языками, следующие языки а также без контекста:

...

  • обращение L

Кажется, это все, что здесь просят. Эти ссылки предлагают дополнительную справочную информацию о том, как получены начальная и последующие закрытые формы.

( Дополнительная, потенциально полезная ссылка из теории множеств )

...