Является ли {

30

Является ли язык { } не зависит от контекста или нет?aibjck | ij,ik,jk

Я понял, что столкнулся почти со всеми вариантами этого вопроса с различными условиями относительно отношений между i, j и k, но не с этим.

Я думаю, что это не является контекстно-свободным, но у вас есть доказательства?

Cem Say
источник
11
@Sariel: Я надеюсь, что это не домашняя проблема, потому что я не знаю, как ее решить.
Цуёси Ито
3
Это похоже на проблему с домашним заданием, поскольку некоторые другие варианты, которые я упоминаю, достаточно легки, чтобы быть домашним заданием. Но этот вариант не является проблемой домашнего задания. Я был бы рад, если кто-нибудь может дать мне ссылку на любой сайт курса, где эта конкретная проблема была назначена в качестве домашней работы.
Cem Say
2
Можете ли вы объяснить, почему стандартные методы не работают?
Уоррен Шуди
3
@ Цуйоши ... Да. Вы правы. Это сложнее, чем кажется.
Сариэль Хар-Пелед
3
Любопытно, что этот язык (и использование леммы Огдена) можно найти в Примере 6.3 (стр. 130) в классической версии Хопкрофта и Уллмана «Введение в теорию автоматов, языков и вычислений».
Доминик Д. Фрейденбергер

Ответы:

28

Лемма Огдена должна работать:

Для данного выберите a i b p c k и отметьте все b (и ничего больше).paibpckb

и k выбраны так, что для каждого выбора того, сколько b на самом деле накачано, есть один показатель накачки, такой, что число b равно i, а другое - где k равно k .ikbbik

То есть и k должны быть из множества 1 n p { p - n + m n m N 0 } .ik1np{pn+mnmN0}

Я вполне уверен, но слишком ленив, чтобы формально доказать, что это множество бесконечно.

Фрэнк Вайнберг
источник
5
Предполагая, что IN_0 означает множество неотрицательных целых чисел, упомянутое множество бесконечно, поскольку оно содержит p + im для i = 0, 1, 2,…, где m - наименьшее общее кратное {1,…, p}.
Цуёси Ито
11
Те, кто не знал лемму Огдена (как и я), могут найти Википедию полезной.
Цуёси Ито
2
@ Цуйоши: Да, ты прав. Я не видел этого простого представления вчера вечером.
Фрэнк Вайнберг
1
Этот ответ размещен в блоге сообщества .
Аарон Стерлинг
Аналогичное доказательство представлено в этом ответе на cs.se.
Сянь-Чи Чанг 之 之
-4

Если отношение между тремя ограничениями - «ИЛИ», то язык - КЛЛ. Решение использует тот факт, что КЛЛ закрыты при объединении. Ясно, что следующие КЛЛ: , L 2 = { a i b j c ki k , j 0 } , L 3 = { а я бL1={aibjckij, k0}L2={aibjckik, j0} (если один не уверен, можно посмотреть на L я как конкатенация CFL и регулярного языканапример,. L 1 является { я б J | я J } сцепляются к { с } .L3={aibjckjk, i0}LiL1{aibjij}{c}

Требуемый язык является объединением указанного выше . Итак, это КЛЛ.L=L1L2L3

R_G
источник
5
Это не правильно. Например, и, следовательно, в вашем L , но a a b c c { a i b j c k | i j , i k , j k } . aabccL1Laabcc{aibjck | ij,ik,jk}
Дейв Кларк
4
Вы предполагаете, что »отношение между тремя ограничениями -« ИЛИ »«, но это не подразумеваемое значение. Все ограничения должны соблюдаться (см. Контрпример Дейва Кларка), и тогда язык не является контекстно-свободным (см. Ответ выше).
DaniCL