Я ищу языки, которые "вероятно, не являются контекстно-свободными", но мы не можем (не) доказать это, используя известные стандартные методы.
Есть недавний опрос на предмет или открытый проблемный раздел от недавней конференции?
Вероятно, не так много языков, которые не известны как CF, поэтому, если вы знаете один, вы также можете опубликовать его в качестве ответа.
Примеры, которые я нашел:
- хорошо известный язык примитивных слов (на нем есть целая приятная недавняя книга: языки без контекста и примитивные слова )
- в Base-K представление совместного домена полинома (см вопрос « Base-K представления о взаимодействии области многочлена - это контекстно-свободное? » на cstheory, которая , возможно , была решена domotorp см его препринт )
Примечание : как показал Арье в своем ответе, вы можете построить целый класс таких языков, если «связать» язык с неизвестной гипотезой о (не) конечности или (не) пустоте некоторых множеств (например, не может быть выражено как сумма двух простых чисел ). Я не совсем заинтересован в таких примерах.
reference-request
big-list
context-free
Марцио де Биаси
источник
источник
Ответы:
Другим хорошим дополнением является дополнение множестваS смежных подслов (или «факторов») последовательности Туэ-Морса T = 0110100110010110 ⋯ . Чтобы дать некоторый контекст, Жан Berstel доказал , что дополнение множества T из префиксов от слова Туэ- Морзе является контекстно-свободной (и на самом деле что - то более общее , чем это). Но соответствующий результат для подслов все еще открыт.
источник
Как насчет языкаLTп двойных простых чисел? Т.е. все пары натуральных чисел ( р , р') (представленные, скажем, в унарном виде), такие, что р , р' и простые, и п'= р + 2 ? Если гипотеза двойных простых чисел верна, то LTп не является контекстно-свободной; в противном случае это конечно.
Редактировать: Позвольте мне дать быстрый набросок доказательства того, что гипотеза двойных простых чисел подразумевает, чтоLTп не является контекстно-свободным. Свяжите с любым языком L его последовательность длины 0 ≤ а1≤ а2≤ … , где целое число ℓ появляется в последовательности, если в L есть слово длины ℓ . Следствием леммы накачки является то, что для L, которые являются регулярными или CFL, последовательность длины удовлетворяет свойству ограниченных разностей: существует R > 0 такое, что a n +L L R > 0 an + 1- аN≤ R для всехN . В теории чисел легко и хорошо известно, что простые числа не имеют ограниченных различий. Наконец, любая бесконечная подпоследовательность последовательности, нарушающая само свойство ограниченных разностей, должна ее нарушать.
источник