Тотални КДА(елементарно)

[Гост]

Много моля някой да даде простичко примерче как от даден тотален детерминиран автомат се строи автомат за допълн. на езика му . Това е нещо като да имаш тотален ДА ,за който α = {a,b}* и да съдържа bb в α ,а допълн на езика му в случая ще е да се построи ТДА,за който α = {a,b}* и да НЕ съдържа bb в α? Или?

[nikko]

Първо поясни какво означава Тотален автомат? Що за превод е това?
Да не би това да е напълно определен ДКА?

[Гост]

Нека имаме КДА А =<бла-бла> . А ще е тотален, ако за всяко а от ∑ и q от Q , \delta (q,a) e дефинирана.
Нямаме нищо фиксирано или зададено...искам измислено примерче,с което условието - по тотален ДА да се построи автомат за допълн. на езика му.

[mkmarinov]

Ако автоматът ти е [tex]A=<\Sigma, Q, s, \delta, F>[/tex] и е тотален, то този, който разпознава [tex]\Sigma* \backslash L(A)[/tex] е [tex]A'=<\Sigma, Q, s, \delta, Q \backslash F>[/tex]. Просто "разменяш" крайните и некрайните състояния. Ясно е защо има изискване да е тотален .
Ако не е тотален - можем много лесно да го допълним до еквивалентен тотален, който е от вида
[tex]A_T = <\Sigma, Q \cup \{ q_{\emptyset} \}, S, \delta_t, F>[/tex], където [tex]\delta_t(q,a)=\delta(q, a)[/tex] когато [tex]q \in Q, \delta (q, a)[/tex] е дефинирано и [tex]\delta_t(q,a)=q_{\emptyset}[/tex] иначе.

[Гост]

Точно това исках да прочета!Мерси )