Можно утверждать, что большинство языков, созданных для описания повседневных проблем, являются контекстно-зависимыми. С другой стороны, возможно и нетрудно найти некоторые языки, которые не являются рекурсивными или даже не рекурсивно-перечислимыми.
Между этими двумя типами находятся рекурсивные, не зависящие от контекста языки. Википедия дает один пример здесь :
Примером рекурсивного языка, который не является контекстно-зависимым, является любой рекурсивный язык, решение которого - сложная задача EXPSPACE, скажем, набор пар эквивалентных регулярных выражений с возведением в степень.
Итак, вопрос: какие существуют другие проблемы, которые разрешимы, но не зависят от контекста? Этот класс задач такой же, как разрешимый EXPSPACE-hard?
formal-languages
complexity-theory
formal-grammars
Виктор Стафуса
источник
источник
Ответы:
CSL такое же , какNSpace(n) (недетерминированная линейное пространство). Любой язык, который находится за пределами , не является CSL.NSpace(n)
Чтобы понять ситуацию, помните, что и даже TQBF.SAT∈NSpace(n)
Есть много проблем. Любая задача, которая завершена для класса сложности, большего, чем подойдет (нам нужен P S p a c e, потому что такие задачи, как TQBF в N S p a c e ( n ) , которые завершены для P S p a a с еPSpace PSpace NSpace(n) PSpace потому что сокращение (полиномиальное время) может взорвать размер ввода полиномом). Дать пример будет означать доказательство нижнего предела для класса сложности, содержащего проблему, и это очень и очень сложная задача. Единственный основной способ сделать это - диагонализация, которая интуитивно означает, что более крупный класс должен иметь возможность имитировать меньший класс.
Таким образом , кажется естественное местом , чтобы начать искать естественные примеры языка , которые не являются CSL.ExpSpace-hard
Нет. По теореме о пространственной иерархии существуют языки, которые находятся в которых нет в N S p a c e ( n ) . Если вы просите хороших примеров, это будет трудно, потому что теорема работает с использованием диагонализации и, следовательно, язык, который она удовлетворяет этим условиям, является очень искусственным.NSpace(n2) NSpace(n)
Я предлагаю вам задать отдельный вопрос для естественной задачи, которая отделяет от N S p a c e ( n ) .NSpace(n2) NSpace(n)
источник
Точно так же, как зависит от контекста, но не является регулярным, язык L = { a n b n c n : n ≥ 0 } разрешим, но не зависит от контекста. Тем не менее, L может быть решен с использованием логарифмического пространства (вам просто нужен счетчик для каждого из символов a , b и c ), поэтому он не является EXSPACE-сложным.{ аNбN: n ≥ 0 } L = { aNбNсN: n ≥0 } L a б с
Кроме того, язык , где r 1 и r 2 являются регулярными выражениями, является PSPACE-полным. Я почти уверен, что это не зависит от контекста, но я не помню доказательств и пишу со своего телефона, так что нелегко искать ссылки.{ ( г1, г2) : L ( r1) = L ( r2) } р1 р2
источник