Контекстно-свободный язык или нет

[Flaminga]

Доброго времени суток. Дан язык $L = \left\lbrace a^ib^jc^kd^l \mid i+k < j+l+3 \right\rbrace$
Доказать, что он контекстно-свободный или обратное.

Варианты на данный момент есть такие:

1)Лемма о накачке(опровергнуть):
взять слово $uvxyz = aabcd$
при $i=2$ получается неравенство 2 < 3 - слово принадлежит языку
накачиваем i, c $i=4$ слово не в языке. Т.е. язык не КС

2)Свести проблему к известной:
знаем, что $L = \left\lbrace a^nb^nc^n \right\rbrace$ не КС, при $i=j=l=n, k=0$ выполняется неравенство $n+0 < n+n+3$ , т.е. слово принадлежит нашему языку. Следовательно,язык не КС

Вот не знаю, насколько оно логично

[Legioner93]

2) чушь, так можно доказать не-КС и языка из всех слов

[Flaminga]

Legioner93 в сообщении #1019128 писал(а):

2) чушь, так можно доказать не-КС и языка из всех слов

Спасибо. Отметаю вариант, а Вы как считаете, он все-таки КС или нет? Может я не в том направлении думаю

[Legioner93]

1) тоже ерунда. Формулировка теоремы начинается с "для любого достаточно длинного слова..."
Т.е. на ограниченных словах вы априори ничего не докажете.

-- Вс май 24, 2015 19:49:47 --

Flaminga в сообщении #1019129 писал(а):

Может я не в том направлении думаю

Ну направления тут видно только два. Либо бы придумыаете грамматику. Либо слово, на котором лемма "не работает". И не забывайте накачивать ВСЕ разбиения заявленного слова, если доказываете не-КС.

[Flaminga]

Legioner93 в сообщении #1019135 писал(а):

1)
Ну направления тут видно только два. Либо бы придумыаете грамматику. Либо слово, на котором лемма "не работает". И не забывайте накачивать ВСЕ разбиения заявленного слова, если доказываете не-КС.

Вроде придумала грамматику, не посмотрите критичным взглядом?

$S \to aAbBcCd$

$A \to aAb$

$B \to bBc$

$C \to cCd$

$A \to a$

$A \to aa$

$A \to b$

$B \to b$

$B \to c$

$B \to cc$

$C \to d$

$A \to e$

$B \to e$

$C \to e$

Т.е. когда мы накапливаем букву с индексом правой части i или k, мы добавляем буквы с индексами j ил l для сохранения неравенства.

[Legioner93]

Ну что-то типа этого. Проверьте сами.
Ваша грамматика порождает только штуки типа $a^i A b^j B c^k C d^l$ с возможным отсутствием заглавных букв.
1) Покажите, что все продукции над этими выражениями сохраняют неравенство (т.к. тремя последними продукциями мы можем удалить нетерминалы) -- значит, мы не получим ничего лишнего (здесь присутствует элемент индукции)
2) Покажите, как получить любое наперед заданное слово языка -- значит, мы получим все слова

-- Вс май 24, 2015 21:28:59 --

Flaminga в сообщении #1019150 писал(а):

Т.е. когда мы накапливаем букву с индексом правой части i или k, мы добавляем буквы с индексами j ил l для сохранения неравенства.

Такое писать вредно. И уж точно не сойдёт за ответ.
Я-то верю, что вы хотели как лучше, а вот какое дело до ваших намерений грамматике? Доказывайте честно.

[Esp_]

На первый взгляд, выглядит как типичный не КС язык.
Попробуйте формально по Теореме Огдена пройтись.

[Flaminga]

Esp_ в сообщении #1019190 писал(а):

На первый взгляд, выглядит как типичный не КС язык.
Попробуйте формально по Теореме Огдена пройтись.

Если возвращаться к версии, что не КС:

$uvxyz = a^ib^jc^kd^l, u = \varnothing, v = a^i, x = b^j, y = c^k, z = d^l$
Накачиваем v и y и выходим за пределы языка. В лемме написано "либо и u и v содержат помеченную позицию, либо её содержат и y и z", т.е. выходит можно, чтобы если y и z были непусты, то u было пусто. Топорно как-то, но вроде по схеме теоремы. Некорректно?

[Flaminga]

whitefox в сообщении #1019289 писал(а):

А следующая грамматика не подойдёт?

$S\rightarrow ABCD\mid aABCD\mid aaABCD\mid ABcCD\mid ABccCD\mid aABcCD$
$A\rightarrow aAb\mid\varepsilon$
$B\rightarrow bB\mid\varepsilon$
$C\rightarrow cCd\mid\varepsilon$
$D\rightarrow dD\mid\varepsilon$

Наверное, стоит добавить

$B\rightarrow \varepsilon$

$D\rightarrow \varepsilon$

А то иначе не получатся слова без b,d

[whitefox]

Flaminga, Вы ответили на уже удалённое сообщение.
Следующая грамматика соответствует Вашему языку:

$S\rightarrow ABC_1C_2D\mid aABC_1C_2D\mid aaABC_1C_2D\mid aABC_1cC_2D\mid$ $ABC_1cC_2D\mid ABC_1ccC_2D\mid E\mid aE_1\mid aaE_2$

$A\rightarrow aAb\mid\varepsilon$
$B\rightarrow bB\mid\varepsilon$
$C_1\rightarrow bC_1c\mid\varepsilon$
$C_2\rightarrow cC_2d\mid\varepsilon$
$D\rightarrow dD\mid\varepsilon$
$E\rightarrow aEd\mid BC_1C_2D\mid BC_1cC_2D\mid BC_1ccC_2D\mid \varepsilon$
$E_1\rightarrow aE_1d\mid BC_1C_2D\mid BC_1cC_2D\mid\varepsilon$
$E_2\rightarrow aE_2d\mid BC_1C_2D\mid\varepsilon$

Очевидно, что для всех слов, порождаемых этой грамматикой, выполняется неравенство $i-j+k-l\leqslant2,$ то есть они принадлежат Вашему языку. Верно и обратное — все слова Вашего языка порождаются данной грамматикой. Следовательно Ваш язык принадлежит КС.

[Flaminga]

whitefox в сообщении #1019313 писал(а):

Flaminga, Вы ответили на уже удалённое сообщение.
Возможно, следующая грамматика соответствует Вашему языку:

$S\rightarrow ABSD\mid aABCD\mid aaABCD\mid aABC_1cD\mid aABcC_2D\mid$ $ ABC_1cD\mid ABcC_2D\mid ABC_1ccD\mid ABccC_2D\mid E\mid aE_1\mid aaE_2$

$A\rightarrow aAb\mid\varepsilon$
$B\rightarrow dB\mid\varepsilon$

Наверное, там $S\rightarrow ABSD и $B\rightarrow bB\mid\varepsilon$

Интересно вышло. Нашла слова, что моему варианту не подходят.

Поэксперементирую с этой, спасибо!

[whitefox]

Да, описка.
Исправил.

[iifat]

Как-то я умудрился упустить эту лемму Огдена. Хотя таки да, она решает.

-- 25.05.2015, 23:38 --

Хотя постойте, помнится, язык конечных автоматов — не КС, а более простой!

[whitefox]

iifat в сообщении #1019402 писал(а):

Хотя постойте, помнится, язык конечных автоматов — не КС, а более простой!

Ну да, регулярный.

[iifat]

В Википедии лемма Огдена доказывается для регулярных языков. Есть другая формулировка? Иначе никакого отношения к вопросу она не имеет, не?