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

Помощ за задача


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


Регистриран на: 04 Jun 2009
Мнения: 5


МнениеПуснато на: Tue Sep 01, 2009 6:15 pm    Заглавие: Помощ за задача

Моля ви помогнете ми за тази задача, никак не ги разбирам а утре имам изпит Sad


Capture.PNG
 Description:
 Големина на файла:  288.81 KB
 Видяна:  1901 пъти(s)

Capture.PNG


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







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

Върнете се в началото
NoThanks
Гост






МнениеПуснато на: Wed Sep 02, 2009 10:06 am    Заглавие:

Имаш граматика с начален нетерминал S и крайна азбука А. Имаш, че S дефинира по следните начини:
1) [tex]S \to \varepsilon[/tex] т.е S е празната дума
2) [tex]S \to A[/tex]
За А пък имаме
1) [tex]A \to babAa[/tex]
2) [tex]A \to cc[/tex]
Сега като прилагаме правило 2) за S получаваме думи от типа S = babAa , където и за А имаме правило. Ясно е, че можем да прилагаме правилата за А до безкрайност. При ново прилагане получаваме S = babbabAaa ; S = babbabbabAaaa и тн. като крайната цел е да получим дума, в която не фигурира А.(другият случай е когато S e празната дума). Тогава за езикът L имаме :[tex]L=\{ \;, cc, babcca, babbabccaa, babbabbabccaaa, ... \; \}[/tex]
Ще е доволно, ако някой покаже как стават б) и в), че аз не съм много навътре в нещата и засега успях само да докажа каква граматика НЕ е за б) , а за в) нямам идея Very Happy
Върнете се в началото
masterfromkardjali
Начинаещ


Регистриран на: 30 Oct 2006
Мнения: 35

Репутация: 14.7

МнениеПуснато на: Thu Sep 03, 2009 11:37 pm    Заглавие:

Граматиката е контекстно-свободна, т.к. имаш продукция в която А седи по средата. Това значи от тип 2 на Чомски-йерархията. За автомат, не мога да ти помогна все още, т.к. за тип 2 не съм учил как се построява. Мога само да кажа, че не е FSM, a Stackmaschine. Другия семестър, ако няма отговор ще ти отговоря Laughing
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
NoThanks
Гост






МнениеПуснато на: Fri Sep 04, 2009 9:55 am    Заглавие:

То това достатъчно ли било Laughing Аз се опитвах да го докажа с pumping лемата, но нещо не ми излизаше Surprised Сега като се замисля, aко си положим [tex]bba = v \; ; a = y \; ; a=z \;ba = u \; ; bcc= x [/tex] имаме, че [tex]|vy| \ge 1 \; |vxy| \le p \le |S|[/tex] и [tex]uv^{i}xy^{i}z[/tex] е в L
Върнете се в началото
masterfromkardjali
Начинаещ


Регистриран на: 30 Oct 2006
Мнения: 35

Репутация: 14.7

МнениеПуснато на: Fri Sep 04, 2009 12:10 pm    Заглавие:

NoThanks написа:
То това достатъчно ли било Laughing Аз се опитвах да го докажа с pumping лемата, но нещо не ми излизаше Surprised Сега като се замисля, aко си положим [tex]bba = v \; ; a = y \; ; a=z \;ba = u \; ; bcc= x [/tex] имаме, че [tex]|vy| \ge 1 \; |vxy| \le p \le |S|[/tex] и [tex]uv^{i}xy^{i}z[/tex] е в L
Еми то не искат да се докаже, а просто да се определи, а то е очевадно, че е контекстно свободен. Според мен може да се мине и без пъмпинг лема, като се използва определението за език от тип 2. В wikipedia, английската има много добро обяснение, какви изисквания Laughing трябва да покрива един език за да е от Тип i
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Дискретната математика Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

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