Я собирался опубликовать это как ответ, но он не отвечает на весь ваш вопрос: дополнением к любому КЛЛ является R (рекурсивный), поскольку рекурсивные языки закрыты при дополнении, а все КЛЛ - R.
Эрик
CFL, не закрываемый при дополнении, не означает, что буква «L» в CFL означает, что его дополнение отсутствует в CFL. Это просто означает, что в КЛЛ
существует буква
@Eric Аскер уже знает, что дополнение к любому КЛЛ является рекурсивным. Они сделали гораздо более сильное утверждение о том , что дополнение любого КЛЛ в P .
Дэвид Ричерби
Ответы:
17
Можно понять ваш вопрос двумя способами, согласно определению «дополнение КЛЛ».
Случай A: Дополнение к CFL - это класс всех языков, которых нет в CFL. Формально,
В этом случае намного больше, чем , у него даже есть языки, которых нет в и т. Д. Но, возможно, это не то, что вы имели в виду.
CFL¯¯¯¯¯¯¯¯¯¯¯={L∣L∉CFL}.
CFL¯¯¯¯¯¯¯¯¯¯¯PR
case B: Определить класс комплемента-CFL как
на словах, набор всех языков , так что дополнение является контекстно-свободным ,
coCFL={L¯∣L∈CFL},
LL
В этом случае то, что вы написали, имеет смысл:
(по алгоритму CYK ), а также (запустить тот же алгоритм, вывести противоположный ответ), а так как , тогда должно быть немедленно, что , верно?CFL⊊PcoCFL⊆PCFL≠coCFLcoCFL⊊P
определение CFK, насколько я понимаю: язык L находится в coCFK тогда и только тогда, когда дополнение L находится в CFK. Под дополнением LI подразумеваются все возможные строки, кроме строк в L. Проблема, я думаю, заключается в том, что дополнение не может быть определено как «запустить тот же алгоритм и перевернуть ответ». Например: L = (x ^ iy ^ iz ^ i) не КЛЛ, но я не знаю, какой алгоритм я могу запустить, чтобы получить (отрицательный) ответ.
user432
1
так что вы имеете в виду случай B. Обратите внимание, что дополнением к CFL может быть не CFL, но это не значит, что алгоритм CYK не работает на нем так же .. Я имею в виду, мы запускаем CYK на , который CFL, и получить ответ для каждого , является ли она в . противоположность этому - ответ на вопрос, находится ли в , хотя может быть не-CFL. ¯ L x ¯ L x L LLL¯¯¯¯xL¯¯¯¯xLL
Ран Г.
1
@ user432 ! coCFL≠CFL¯¯¯¯¯¯¯¯¯¯
Рафаэль
1
@RanG - это ваш стандарт обозначений здесь? Я бы ожидать и ¯ C F L = класс языков L такое , что L ∉ C F L . с о СFL = { L : L¯∈ CFL}CFL¯¯¯¯¯¯¯¯¯¯¯=LL∉CFL
Усул
1
На самом деле, позвольте мне изменить обозначения в соответствии с вашим предложением, это будет иметь больше смысла.
Ран Г.
3
Надежным классом, который содержит как CFL, так и coCFL, является LOGCFL , который содержит все языки, приводимые в пространстве журнала к контекстно-свободному языку. Этот класс является промежуточным между NL и AC1 и имеет некоторые естественные полные проблемы. Это также может быть определено в терминах ограниченных цепей AC1. LOGCFL закрывается при дополнении (это расширение аргумента, используемого, чтобы показать, что NL = coNL).
Дополнением к КЛЛ может быть КЛЛ, но это не обязательно так. Дополнение CFL является и рекурсивным (R), и рекурсивным перечислимым (RE). Почему? Все КЛЛ являются как R, так и RE. Языки R закрыты в дополнении (но RE - нет). В этом контексте дополнением к CFL является R, который по своей природе является RE.
Спрашивающий уже сказал , что они знают , что дополнение любого УНЧ в P . Это гораздо более сильное утверждение, чем рекурсивное или RE. Как будто спрашивающий упомянул человека, который не может ходить, а вы ответили доказательством того, что он не может бежать со скоростью звука.
Ответы:
Можно понять ваш вопрос двумя способами, согласно определению «дополнение КЛЛ».
Случай A: Дополнение к CFL - это класс всех языков, которых нет в CFL. Формально, В этом случае намного больше, чем , у него даже есть языки, которых нет в и т. Д. Но, возможно, это не то, что вы имели в виду.
case B: Определить класс комплемента-CFL как на словах, набор всех языков , так что дополнение является контекстно-свободным ,
В этом случае то, что вы написали, имеет смысл: (по алгоритму CYK ), а также (запустить тот же алгоритм, вывести противоположный ответ), а так как , тогда должно быть немедленно, что , верно?CFL⊊P coCFL⊆P CFL≠coCFL coCFL⊊P
источник
Надежным классом, который содержит как CFL, так и coCFL, является LOGCFL , который содержит все языки, приводимые в пространстве журнала к контекстно-свободному языку. Этот класс является промежуточным между NL и AC1 и имеет некоторые естественные полные проблемы. Это также может быть определено в терминах ограниченных цепей AC1. LOGCFL закрывается при дополнении (это расширение аргумента, используемого, чтобы показать, что NL = coNL).
источник
Дополнением к КЛЛ может быть КЛЛ, но это не обязательно так. Дополнение CFL является и рекурсивным (R), и рекурсивным перечислимым (RE). Почему? Все КЛЛ являются как R, так и RE. Языки R закрыты в дополнении (но RE - нет). В этом контексте дополнением к CFL является R, который по своей природе является RE.
источник