Прокачка леммы в контекстно-свободных языках

A = {0^a 1^b 2^c | a < b < c}

Мне нужно показать, что A не зависит от контекста. Я предполагаю, что для этого мне нужно использовать лемму о накачке, но как?


computation-theory context-free-grammar pumping-lemma
person Clint    schedule 04.11.2010    source источник
comment
Похоже, это домашнее задание, если да, добавьте тег домашнего задания.   -  person Daniel Renshaw    schedule 04.11.2010
comment
Перейти на cstheory.stackexchange.com?   -  person Sven Marnach    schedule 04.11.2010
comment
Я сомневаюсь, что людям из cstheory.SE этот вопрос будет интересен.   -  person P Shved    schedule 04.11.2010
comment
Мне несколько раз рекомендовали cstheory.stackexchange, и у них довольно строгая политика запрета домашних заданий. Они расстраиваются, когда люди публикуют домашние задания, и SO расстраивается (по понятным причинам), когда люди публикуют задачи, не связанные с программированием.   -  person prelic    schedule 05.11.2010
comment
Если вы хотите, чтобы лемма о перекачке применялась к очень похожему языку, вот ответ, который я дал на недавний вопрос о лемме о перекачке CFL: stackoverflow.com/questions/4149357/   -  person William    schedule 12.11.2010

Ответы (2)


arrow_upward
2
arrow_downward

Цель состоит в том, чтобы доказать, что для любой колонны, длина которой> = минимальной длине откачки, струна не может быть закачана. То есть, если вы разделите его на подстроки uvxyz, строка, полученная в результате создания копий (или удаления копий) v и y, все еще будет на языке A.

Обратите внимание, что вам нужно только показать, что одна строка на языке не может быть накачана (если она соответствует минимальной длине накачки p).

Рассмотрим этот язык и его отношение к A:

alt text

person prelic    schedule 05.11.2010

arrow_upward
0
arrow_downward

Шаг первый: определите минимальную длину откачки (2 ^ p + 1), где p - количество переменных. Шаг второй: сделайте несколько ниток такой длины. Шаг третий: начните разрезать строки на vwxyz так, чтобы | wy ​​|> 0 (обратите внимание, что | x | МОЖЕТ быть нулевым) и | wxy | ‹= 2 ^ p + 1. Посмотрите на различные способы определения w и y и на то, что происходит, когда вы начинаете повторять эти подстроки на месте.

Ключ, вероятно, будет на разделительной линии между 0 и 1.

person philosodad    schedule 05.11.2010