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

L не е контекстно-свободен език


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


Регистриран на: 13 Apr 2008
Мнения: 91

Репутация: 11.8
гласове: 2

МнениеПуснато на: Sun May 31, 2009 12:49 pm    Заглавие: L не е контекстно-свободен език

Да питам така ли се решава и ако не как трябва да се реши.
зад.1.
Да се докаже, че L не е контекстно-свободен език:
[tex]L=\left\{ a^n b^m c^k | n<m<k\in N\right\}[/tex]
Доказателство:
Нека допуснем, че L е контекстно-свободен език => [tex]w=a^n b^{n+1} c^{n+2} w\in L[/tex] ,защото [tex]|w|=3n+3 \ge n[/tex].
Нека w=uvxyz от Pumping lemma(Лемата за показчването ) =>
[tex]1)|vxy|\le n[/tex]
[tex]2)|vy|\ge 1[/tex]
[tex]3)\cyr{Za vsyako} i\in N , uv^ixy^iz\in L[/tex]
[tex]3n+3=|w|=|u|+|vxy|+|z|\le n+|u|+|z|[/tex]
[tex]2n+3\le |u|+|z|[/tex]
[tex]1.\cyr{sl.} |u|\ge n \cyr{ i 2.sl.} |z|\ge n+[/tex]3
[tex]1.\cyr{sl.} |u|\ge n[/tex]
[tex]\cyr{V } w=uvxyz ,u [/tex] е представка и тъй като [tex]w=a^n b^{n+1} c^{n+2}=>u=a^nS,\cyr{k\cdprimedeto } S\in b^*c^*[/tex]
Нека [tex]w=uv^0xy^0z=>3n+3=|uxz|+|vy|\le |uxz|+n[/tex]
[tex]2n+3\le |w|[/tex]
[tex]|w|\ge 2n+3[/tex]
[tex]\cyr{I }[/tex],
[tex]3n+3\ge |uxz|+n[/tex]
[tex]3n+2\ge |w|[/tex]
но [tex]w=a^n\beta \cyr{ i } |w|\le 3n+2=>\beta\le 2n+2,\cyr{ no } \beta=b^mc^k \cyr{ i } [/tex][tex]k>m>n=>[/tex] ,тъй като [tex]k,m,n\in N[/tex] ,то
[tex]m>n<=>m\ge n+1[/tex]
[tex]k>m<=> k\ge m+1<=>k\ge n+2=>[/tex]
[tex]|\beta|\ge n+1+n+2=2n+3=> [/tex]противоречие с [tex]\beta\le 2n+2.[/tex]
[tex]\cyr{ 2.sl.} |z|\ge n+3[/tex]
z надставка в [tex]w =>z=tc^{n+2},t\ge 1,t\in \left\{b^+a^*\right\}[/tex]
2.1.сл. [tex]u=a^nS ,|s|\ge 0,S\in b^*[/tex]
2.2.сл.във v y не съдържа а-та
2.3 сл.във v y съдържа поне 1 а-та

2.1. го изпускам
2.2.[tex]z=tc^{n+2}=>[/tex]в vxy няма с-та
v y не съдържа а-та
Нека [tex]w=uv^0xy^0z=>w\in L \cyr{ ot } P.Lemma =>|vy|\ge 1=>[/tex]в |vy|има повече от 1 б-та и в uxz броят на б-та е равен на броят на б-та в [tex]|uvxyz| -|b[/tex]| в |vy|=> |b| в w е не повече от n=> n!<n=> противоречие
2.22.
v y съдържа поне едно а, [tex]vxy\in[/tex] {[tex]a^+b^+[/tex]}
Нека i=2
[tex]w=uv^2xy^2z[/tex] ,но |[tex]w|=|uvxyz|+|vy| [/tex],но [tex]|vy|\ge[/tex] 1 и в vy има поне 1 б-та и 1 -та => в w броят на б-та е поне с 1 по-голям =>n+1+1!<n+2=> противоречие

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







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

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


Регистриран на: 13 Apr 2008
Мнения: 91

Репутация: 11.8
гласове: 2

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

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

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