2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Контекстно-свободный язык или нет
Сообщение24.05.2015, 17:44 


27/05/13
31
Хабаровск
Доброго времени суток. Дан язык $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$ , т.е. слово принадлежит нашему языку. Следовательно,язык не КС

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

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение24.05.2015, 19:37 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение24.05.2015, 19:40 


27/05/13
31
Хабаровск
Legioner93 в сообщении #1019128 писал(а):
2) чушь, так можно доказать не-КС и языка из всех слов

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

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение24.05.2015, 19:46 
Заслуженный участник
Аватара пользователя


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

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

Flaminga в сообщении #1019129 писал(а):
Может я не в том направлении думаю

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

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение24.05.2015, 21:02 


27/05/13
31
Хабаровск
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 для сохранения неравенства.

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение24.05.2015, 21:27 
Заслуженный участник
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение24.05.2015, 23:27 


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

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение25.05.2015, 08:13 


27/05/13
31
Хабаровск
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 было пусто. Топорно как-то, но вроде по схеме теоремы. Некорректно?

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение25.05.2015, 09:21 


27/05/13
31
Хабаровск
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

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение25.05.2015, 11:06 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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,$ то есть они принадлежат Вашему языку. Верно и обратное — все слова Вашего языка порождаются данной грамматикой. Следовательно Ваш язык принадлежит КС. :D

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение25.05.2015, 12:05 


27/05/13
31
Хабаровск
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$

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

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

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение25.05.2015, 15:22 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Да, описка. :oops:
Исправил.

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение25.05.2015, 15:34 
Заслуженный участник


16/02/13
4214
Владивосток
Как-то я умудрился упустить эту лемму Огдена. Хотя таки да, она решает.

-- 25.05.2015, 23:38 --

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

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение25.05.2015, 15:40 
Заслуженный участник
Аватара пользователя


19/12/10
1546
iifat в сообщении #1019402 писал(а):
Хотя постойте, помнится, язык конечных автоматов — не КС, а более простой!

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

 Профиль  
                  
 
 Re: Контекстно-свободный язык или нет
Сообщение25.05.2015, 16:07 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: worm2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group