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

Проблем с еднo твърдение, свързано с минимизация


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


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

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

МнениеПуснато на: Wed May 27, 2009 12:00 pm    Заглавие: Проблем с еднo твърдение, свързано с минимизация

L = (ba U ab)*
Нека M = <K, ∑, δ, S, F> - КДА, x ~my , (x, y Є ∑*) <=> (s, x) |-m*(q, ε) и (s, y) |-m*(q, ε), q Є K;

E(q) = { x | x Є ∑* & (s, x) |-m*(q, ε) }

Ето проблема:
E(q1) = (ba)* -> това ми е ясно..
Е(q2) = La -> това не и всяко следващо не го разбирам..
Е(q3) = (La)*abL
E(q4) = (ba)*b
.......

Някой, ако може да ми помогне, да го разбера ще съм му много благодарен Smile
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







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

Върнете се в началото
nikko1
Напреднал


Регистриран на: 23 Nov 2008
Мнения: 422

Репутация: 61.8
гласове: 36

МнениеПуснато на: Thu May 28, 2009 10:09 pm    Заглавие:

Е то хубаво ще обясняваме минимизация на ДКА, реализиращ формалният език L, ама все пак трябва да дадеш и самия автомат. Дали ще бъде с таблица на преходите или с диаграма, той е нужен Smile
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
complex
Напреднал


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

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

МнениеПуснато на: Fri May 29, 2009 12:02 pm    Заглавие:

Ето това е автоматът. Помагайте Smile


dsadasda.JPG
 Description:
 Големина на файла:  17.44 KB
 Видяна:  1577 пъти(s)

dsadasda.JPG


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


Регистриран на: 23 Nov 2008
Мнения: 422

Репутация: 61.8
гласове: 36

МнениеПуснато на: Fri May 29, 2009 10:48 pm    Заглавие:

Не е пълен автомата, не трябва ли q_1 да е начално и заключително, а също така и q_3 да е заключително?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
complex
Напреднал


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

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

МнениеПуснато на: Sat May 30, 2009 12:57 pm    Заглавие:

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


Регистриран на: 23 Nov 2008
Мнения: 422

Репутация: 61.8
гласове: 36

МнениеПуснато на: Sun May 31, 2009 5:54 pm    Заглавие:

Сега след като уточнихме условието вече е време за обяснение. E(q_i) представлява регулярния език при който дадения автомат се намира в състояние q_i. Първо очевидно е, че от състояние q_5, което е незаключително няма изходящи преходи. Очевидно това състояние е използвано за всеки преход, който се получава при дума, която задължително не е от езика, напр. aa или bb.
След като започваме в състояние q_1 (следователно [tex]\epsilon\in E(q_1)[/tex] и в q_1 има само един входящ преход, който е [tex]\delta(q_4,a)=q_1[/tex] и така може с индукция да се докаже, че [tex]E(q_1)=(ba)^*[/tex]. Да определим [tex]E(q_4)[/tex] в състояние q_4 има само един входящ преход, който е [tex]\delta(q_1,b)=q_4[/tex] и така [tex]E(q_4)=E(q_1)b=(ab)^*b.[/tex]
В състояние q_2 се отива по два начина, като и двата прехода са със символа [tex]a[/tex], така че [tex]E(q_2)=E(q_1)a\cup E(q_3)a=(ab\cup E(q_3))^*a.[/tex]
За да стигнем обаче до състояние q_3 задължително трябва да минем през q_2 (другият входящ преход в q_3 е през q_6, който се достига само през q_3). Така [tex]E(q_2)=(ba)^*(ab)^*a\subseteq La[/tex], от което веднага се вижда, че [tex]E(q_3)=(ba)^*((ab)^*\cup (ba)^*)^*=L[/tex] и следователно [tex]E(q_2)=(ab\cup E(q_3))^*a=(ab\cup L)^*a=La.[/tex]
До q_6 се достига само чрез [tex]\delta(q_3,b)=q_4[/tex] следователно [tex]E(q_6)=E(q_3)b=Lb[/tex]
Така [tex]q_1\equiv q_3[/tex] и [tex]q_4\equiv q_6[/tex] и минималният апарат ще има 4 вътрешни състояние [tex]q_1\equiv q_3,\, q_2,\, q_4\equiv q_6[/tex] и [tex]q_5[/tex].
Така се получава автоматът на картинката.



minimal.png
 Description:
 Големина на файла:  39.79 KB
 Видяна:  1552 пъти(s)

minimal.png


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


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

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

МнениеПуснато на: Sun May 31, 2009 10:39 pm    Заглавие:

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

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