Регистрирайте сеРегистрирайте се

Задача свързана с контекстно-свободнa граматикa


 
   Форум за математика Форуми -> Дискретната математика
Предишната тема :: Следващата тема  
Автор Съобщение
complex
Напреднал


Регистриран на: 08 Nov 2007
Мнения: 296

Репутация: 31.9Репутация: 31.9Репутация: 31.9
гласове: 6

МнениеПуснато на: Thu Jun 04, 2009 5:48 pm    Заглавие: Задача свързана с контекстно-свободнa граматикa

Ще ви помоля да ми помогнете за следната задача:
G=?, така че L(G) = {anbm| n ≥ m} = {akambm|k, m ≥ 0}
R={S`-> SA, S -> ε, S -> aS, A -> ε, A -> aAb }
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
BeckhamStZ
Начинаещ


Регистриран на: 03 Apr 2008
Мнения: 86

Репутация: 11.4
гласове: 3

МнениеПуснато на: Sat Jun 06, 2009 1:59 pm    Заглавие:

А какво е условието? Да се намери граматиката ли?

G' = L(G') = a*
G" = L(G") = { [tex]a^{n}b^{n}[/tex] | [tex]n \in N[/tex] }
G" = { {S}, {a,b}, S, { S -> [tex]\epsilon[/tex], S->aSb }

G = L(G) = L(G') . L(G")

от КДА A построяване на КСГ разпознаваща съответния език
GA = < Q, ∑, S, {q1 -> aq2 | [tex]\delta[/tex](q1,a)=q2} U { q -> [tex]\epsilon[/tex] | [tex]q \in F[/tex]} >
=> G' = {q0, {a,b}, q0, { q0 -> aq0, q0-> [tex]\epsilon[/tex]}

и се прави конкатенацията
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
complex
Напреднал


Регистриран на: 08 Nov 2007
Мнения: 296

Репутация: 31.9Репутация: 31.9Репутация: 31.9
гласове: 6

МнениеПуснато на: Mon Jun 08, 2009 9:09 pm    Заглавие:

Мерси колега, разбрах ги Smile
Ако може да помоля да ми помогнете и за следващата задача:
Да се докаже, че езикът не е контекстно-свободен.
L = {bmckdmen | n > k}
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
BeckhamStZ
Начинаещ


Регистриран на: 03 Apr 2008
Мнения: 86

Репутация: 11.4
гласове: 3

МнениеПуснато на: Mon Jun 08, 2009 9:22 pm    Заглавие:

Това ще стане със Pumping lemma-та, ама само до тук мога да ти помогна Smile още не съм я разбрал. Иначе откъде ги имаш тези задачи? Днеска на контролното ( СИ - ФМИ ) ни бяха такива задачите
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
complex
Напреднал


Регистриран на: 08 Nov 2007
Мнения: 296

Репутация: 31.9Репутация: 31.9Репутация: 31.9
гласове: 6

МнениеПуснато на: Mon Jun 08, 2009 10:08 pm    Заглавие:

Хаха.. е точно от там, че писах некви глупости и ми е интересно как ще стане.. поне за изпита да ги напиша като хората.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
BeckhamStZ
Начинаещ


Регистриран на: 03 Apr 2008
Мнения: 86

Репутация: 11.4
гласове: 3

МнениеПуснато на: Tue Jun 09, 2009 3:31 am    Заглавие:

oo то и аз днеска нищо не направих Smile ама и понеделник е ден...
аз днеска нищо не направих. коя група си?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
complex
Напреднал


Регистриран на: 08 Nov 2007
Мнения: 296

Репутация: 31.9Репутация: 31.9Репутация: 31.9
гласове: 6

МнениеПуснато на: Tue Jun 09, 2009 3:10 pm    Заглавие:

Така ли се решава задачата..?

{bmckdmen | n > k}

1сл. m ≥ n > k
Нека n е числото от лемата и L e CF. Тогава w = bmcndmen+1, тогава w=2n +1>n, следователно w = xyzuv, |yzu|≤n, |yu|≥1 и за всяко i е изпълнено xyizuiv Є L.
1.1 |yzu| = bk, тогава x = bs, v = bm-(k+s)cndmen+1, нека |yu|=bp, като p ≥ 1, тогава при и i = 0 xy0zu0v = bsbk-pbm-k-scndmen+1 = bm-pcndmen+1 < w = bmcndmen+1, т.к p≥1, следователно гори..
1.2 |yzu| = bkct, x = bm-k, v = cn-tdmen+1 , нека |yu|b=p, |yu|c=q , т. че p+q ≥ 1, тогава при i = 0 xy0zu0v = bm-kbk-pct-qcn-tdmen+1 = bm-pcn-qdmen+1 < w = bmcndmen+1, т.к в противан случай p = 0, q = 0 следователно гори..
2сл. n>k>m
Нека n е числото от лемата и L e CF. Тогава w = bncn+1dnen+2, тогава w=4n +3>n, следователно w = xyzuv, |yzu|≤n, |yu|≥1 и за всяко i е изпълнено xyizuiv Є L.
1.1 - аналог.
1.2 - аналог.


Последната промяна е направена от complex на Tue Jun 09, 2009 8:57 pm; мнението е било променяно общо 1 път
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
1-vi klas
Начинаещ


Регистриран на: 19 May 2008
Мнения: 29

Репутация: 5.6Репутация: 5.6Репутация: 5.6Репутация: 5.6Репутация: 5.6

МнениеПуснато на: Tue Jun 09, 2009 5:02 pm    Заглавие:

леле аз кви глупости си измислях на тая..дано поне за творчество има 50-тина стотни и 1 единица ,че успях да си намеря мястото, на което да седна + 50 стотни за 1-ва задача .. заслужавам 4 Laughing
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Дискретната математика Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2021 math10.com.