Пәнін оқыту-әдістемелік кешен 5В060200 «Информатика» мамандығына арналған ОҚУ-Әдістемелік материалдар


Алгоритм 3.2. СА эквивалентті күйінің бірігуі



жүктеу 2,68 Mb.
бет106/127
Дата19.11.2018
өлшемі2,68 Mb.
#20473
1   ...   102   103   104   105   106   107   108   109   ...   127

Алгоритм 3.2. СА эквивалентті күйінің бірігуі

Кіру КА M′′ = (Q, T, F, H, Z) жетіспеушіліксіз қалыпта

Шығу: Минимальды СА М" = (Q′, T, F′, H, Z′).

Қадам 1. Бірінші қадамда нөлдік R(0) бөлінуін құрамыз, эквивалентті екі класстан тұратын: СА - Z қорытынды қалпы және Q-Z қорытынды емес қалпы..

Қадам 2. Өткен қадамда R(n) бөлінуін эквивалентті класста бұрынғы күйіне қосылады, олар біркелкі кіру символымен n-1 эквивалентті қалыпқа өтеді

R(n) = {ri(n): {qij cQ:VtcTF(qij,t) ⊆ гДи-1)} Vi, j∈N}.

Қадам 3. Әзірше R(n) R(n-1 орындалғанша n:=n+1 деп ойлап, қадам 2 – ге өтеміз.

Қадам 4. Қалған бөлінбеген топтардың күйімен және автоматтың жаңа кестесіне енгіземіз.

Қадам 5. СА M эквивалентін анықтап, жаңа енгізулер енгіземіз.



Мысал 3.2 Мысалдағы3.1. СА минималдаймыз. Онда мынаны аламыз:

R(0)={{A,B,C},{D,E}},n = 0;

R(1)={{A},{B,C},{D,E}},n = 1;

R(2)={{A},{B,C},{D,E}},n=2.

R(1) = R(2),

Бөлінбеген топтардың қалпын белгілейміз: X={B,C},Y={D,E}.

M минималды автоматтын аламыз, мұндағы Q′′={A,X, Y}, Z={Y}.

Функцияның M′′ автоматына өтуі кесте 3.3. көрсетілген



Кесте 3.3 - Функцияның M автоматына өтуі

F′′

А

X

Y

а

X




X

Ъ

X

Y

Y

СА минимизациядан кейінгі өтуі сурет3.3-те графы көрсетілген.

Сурет 3.3 – СА M′′ минималды өтуі


3 зертханалық жұмысқа орындау тапсырмалары
Программалық жабдықты өңдеп, келесі функцияларды ұйымдастырамыз:

1) СА шығуын және экран бетінде қорытындысының графы болуы керек;

2) СА жетіспеген қалпын шығару;

3) СА эквивалентті қалпын шығару;

4) Минималды СА графын экран бетіне шығару.

5) Алгоритмге арналған тестер бақылау мысалдарының сериясын өңдейміз.


3 зертханалық жұмысқа орындау тапсырмалары сурет3.4 берілген

жүктеу 2,68 Mb.

Достарыңызбен бөлісу:
1   ...   102   103   104   105   106   107   108   109   ...   127




©g.engime.org 2024
әкімшілігінің қараңыз

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау