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
1178
2) чушь, так можно доказать не-КС и языка из всех слов

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


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

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

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


28/07/09
1178
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
1178
Ну что-то типа этого. Проверьте сами.
Ваша грамматика порождает только штуки типа $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
4105
Владивосток
Как-то я умудрился упустить эту лемму Огдена. Хотя таки да, она решает.

-- 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
4105
Владивосток
В Википедии лемма Огдена доказывается для регулярных языков. Есть другая формулировка? Иначе никакого отношения к вопросу она не имеет, не?

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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