Является ли язык { } не зависит от контекста или нет?
Я понял, что столкнулся почти со всеми вариантами этого вопроса с различными условиями относительно отношений между i, j и k, но не с этим.
Я думаю, что это не является контекстно-свободным, но у вас есть доказательства?
Ответы:
Лемма Огдена должна работать:
Для данного выберите a i b p c k и отметьте все b (и ничего больше).p aibpck b
и k выбраны так, что для каждого выбора того, сколько b на самом деле накачано, есть один показатель накачки, такой, что число b равно i, а другое - где k равно k .i k b b i k
То есть и k должны быть из множества ⋂ 1 ≤ n ≤ p { p - n + m ∗ n ∣ m ∈ N 0 } .i k ⋂1≤n≤p{p−n+m∗n∣m∈N0}
Я вполне уверен, но слишком ленив, чтобы формально доказать, что это множество бесконечно.
источник
Если отношение между тремя ограничениями - «ИЛИ», то язык - КЛЛ. Решение использует тот факт, что КЛЛ закрыты при объединении. Ясно, что следующие КЛЛ: , L 2 = { a i b j c k ∣ i ≠ k , j ≥ 0 } , L 3 = { а я бL1={aibjck∣i≠j, k≥0} L2={aibjck∣i≠k, j≥0}
(если один не уверен, можно посмотреть на L я как конкатенация CFL и регулярного языканапример,. L 1 является { я б J | я ≠ J } сцепляются к { с } ∗ .L3={aibjck∣j≠k, i≥0} Li L1 {aibj∣i≠j} {c}∗
Требуемый язык является объединением указанного выше . Итак, это КЛЛ.L=L1∪L2∪L3
источник