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

[complex]

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(q₁) = (ba)* -> това ми е ясно..
Е(q₂) = La -> това не и всяко следващо не го разбирам..
Е(q₃) = (La)*abL
E(q₄) = (ba)*b
.......

Някой, ако може да ми помогне, да го разбера ще съм му много благодарен

[Реклама]

[nikko1]

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

[complex]

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

[nikko1]

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

[complex]

Опсс.. много се извинявам, но съм се разсеял нещо и не съм дал началното и заключителните състояния. Оправих ги, така са.

[nikko1]

Сега след като уточнихме условието вече е време за обяснение. 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].
Така се получава автоматът на картинката.

[complex]

Много ти благодаря за изчерпателното и ясно обяснение. Изясни ми се всичко