Бесконтекстный язык или нет? Я могу писать грамматику, но не использую лемму о накачке

У меня есть язык: L = {0 ^ i 1 ^ i | я> = 0}

Грамматика, описывающая его, доказывает, что это контекстно-свободный язык: S -> 0S1 | е

Если язык контекстно-свободный, должна выполняться лемма о перекачке. Однако я не могу заставить его работать, независимо от того, что я выберу для «прокачки», я получу смесь нулей и единиц, например 0101.

Правильно ли я, что это действительно контекстно-свободный язык? Если да, то не могли бы вы привести пример использования леммы о накачке?


context-free-grammar pumping-lemma
person Kent Munthe Caspersen    schedule 30.05.2013    source источник
comment
Для языков CF вы выбираете две строки для накачки (выражаете строку на языке как uvxyz, затем накачиваете обе v и y). Таким образом, выбор v и y, удовлетворяющих условиям леммы CF о накачке, должен быть тривиальным, и в этом примере доказательство сработает. (Подсказка: x будет пустой строкой.)   -  person Jim Lewis    schedule 31.05.2013
comment
Кроме того, вы должны знать, что, хотя вы можете использовать CFPL для доказательства того, что язык не контекстно-зависимый, доказательство не работает в другом направлении.   -  person Jim Lewis    schedule 31.05.2013
comment
У меня s = uvxyz, вы можете показать, как вы хотите разделить строку на L, чтобы ее можно было накачать? Даже если я выберу v или y как пустые, не оба они могут быть пустыми, и в конечном итоге я что-то накачу. Я также могу выбрать прокачку только 0, получить больше 0, чем 1 - только 1, получить больше 1, чем 0 - и 0, и 1 дают мне ... 0101 ... при прокачке.   -  person Kent Munthe Caspersen    schedule 31.05.2013
comment
вы пробовали v = '0', x = e, y = '1'? v и y «прокачиваются» равное количество раз, если вы используете CFPL.   -  person Jim Lewis    schedule 31.05.2013
comment
@KentMuntheCaspersen (1) Эти леммы могут использоваться, чтобы определить, не ли конкретный язык в данном языковом классе. Однако их нельзя использовать для определения принадлежности языка к данному классу, поскольку выполнение леммы о перекачке является необходимым, но не достаточным условием для членства в классе. Ссылка (2) Прочтите: Лемма по накачке для CFG сомнений   -  person Grijesh Chauhan    schedule 31.05.2013
comment
Когда v = '0', x = e, y = '1', я ошибочно понял, что это даст строку вида 010101 ... которой нет в L. Спасибо за ваш ответ, это очистило мой разум. Я понимаю, что лемма о перекачивании верна для всех языков, свободных от контекста, а также для некоторых языков, не зависящих от контекста, поэтому вы не можете доказать, что язык является контекстно-свободным, используя лемму о перекачке. Однако, учитывая, что мы знаем, что язык L контекстно-зависимый, лемма о накачке все еще должна выполняться. Поэтому должно быть решение, найденное @JimLewis.   -  person Kent Munthe Caspersen    schedule 31.05.2013
comment
@KentMuntheCaspersen, ваш комментарий сбивает меня с толку :( .. Это тоже меня?   -  person Grijesh Chauhan    schedule 31.05.2013
comment
Частично вы говорите, что лемму о накачке нельзя использовать, чтобы показать, что конкретный язык является контекстно-свободным. Вы правы, но меня это не касается. В этом случае я уже знаю, что язык контекстно-свободный, и поэтому должна выполняться лемма о накачке. @JimLewis нашел правильное решение того, как Лемма о перекачивании может удерживать этот язык.   -  person Kent Munthe Caspersen    schedule 31.05.2013

Ответы (1)


arrow_upward
0
arrow_downward

Если вы можете описать язык с помощью контекстно-свободной грамматики, то этот язык не зависит от контекста. Было бы сложно доказать, что язык контекстно-зависимый, используя лемму о накачке, потому что даже если вы найдете строку, которую можно накачать, все равно может быть строка, которую нельзя накачать.

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

Вот пример строки в L = {0 ^ i 1 ^ i | i> = 0} и как его можно прокачать.

строка w = 01, может быть разбита следующим образом:

u = empty   
v = 0  
x = empty  
y = 1   
z = empty

u v ^ i x y ^ i z находится в L для каждого i> = 0

person Garrison    schedule 18.11.2013
comment
Правильно, что лемма о накачке в основном используется для доказательства того, что язык является контекстно-свободным. Вы говорите, что с помощью леммы о перекачке может быть сложно доказать, что язык контекстно-свободный. На самом деле это невозможно, поскольку лемма о накачке также верна для некоторых языков, которые не являются контекстно-независимыми. В этом случае мы уже знаем, что язык L контекстно-свободный (я написал для него грамматику), и вы только что показали строку, которую можно перекачивать, что я и просил. Спасибо. - person Kent Munthe Caspersen; 18.11.2013