Зертханалық жұмыс №3
Дербес автоматтар және олардың минимизациясы
Мазмұны: «Автоматтардың эквиваленттілігі», «минимальді шекті автомат» түсінігін енгізу, детерминантты шекті автоматтарды минимизациялауды дағдыландыруды қалыптастыру.
Мақсаты: - «Соңғы автоматтың жетіспеуі», «Автоматтың эквивалентті күйі», «Соңғы автоматтың минималы» түсініктерін қалыптастыру;
-Соңғы автоматтың детерминирлеген минимизациясын меңгеру.
Негізгі теориялар
Соңғы автоматтың 2-і типі бар: Эквивалентті күй және жетіспеушілік күй.
Анықтама 3.1.Соңғы автоматтын М = (Q, T,F, H, Z) екі q және q′ әртүрлі күйлер n эквивалентті деп аталады. Егер осылардың бір күйінде орналасып, ω: VT* , |ω|≤n, символының тізбегіне кірсе. Онда автоматтың соңғы күйлердің біреуіне өтуіне мүмкіндік бар.
Анықтама 3.2.Соңғы автоматтың q күйінің жетіспеуі- егерде автоматтың басты күйінен оған жолы болмауы.
Анықтама 3.3. Эквивалентті және жетіспеу күйі сақталмайтын СА – минималды автомат деп аталады.
Алгоритм 3.1.СА қалыпының жетіспеуі
Кіру: КА М = (Q, T, F, H, Z).
Шығу КА)M′ = (Q′, T, F′, H, Z′).
Қадам1.Соңғы автоматтың бастапқы қалпын Qд қалып тізіміне орналастыру керек, сонда Qд0=H шығады.
Қадам2.Жаңа элементтер үшін тізімдегі қалыпты толтыру үшін қолданылады.
Қадам 3.2-ші қадамды қайталау, қалыпқа жеткен тізім ауыстырылуы тоқталмағанша , егер Qд ф Q-f сонда i:=i+1, әйтпесе Qд =Qдi
Қадам4. Q жиынындағы СА қалпын щығару үшін Qд қалыпқа жеткен . Q′ = Q ∩ Qд болмайды.
Қадам 5.Соңғы қалыпқа және функция жұбына өтуді шектеу, жеткіліксіз күйді құрайды. Z′ = Z ) = p|q (Q−Qд)}.
Мысал 3.1. Жеткіліксіз СА күйін М = (Q, T, F, H, Z), мұндағы Q = {A, B, C, D, E,F,G},T= {a, b}, H= {A},Z= {D, E} және 3.1. кестесінде көрсетілген.
Кесте 3.1 – СА функциясының өтуі.
F
|
А
|
В
|
С
|
D
|
Е
|
F
|
G
|
а
|
В
|
|
|
С
|
В
|
D
|
F
|
Ь
|
С
|
D
|
Е
|
Е
|
D
|
G
|
Е
|
Сурет 3.1 М соңғы автоматтының шығу графы.
Бірізділік СА жетіспеуі мына түрде:
Q0={A};
Q1 = {A,B,C};
Q2={A,B,C,D,E};
Q3 = {A, B, C, D, E}; Q2 = Q3, онда Qд = {A, B, C, D, E}.
Qн={F, G }; Q′= {A,B, C,D,E}; Z′= {D,E}.
Функцияның M автоматына өтуі кесте3.2. көрсетілген
Кесте3.2 – Функцияның M автоматына өтуі
-
F
|
А
|
В
|
С
|
D
|
Е
|
а
|
В
|
|
|
С
|
В
|
Ъ
|
С
|
D
|
Е
|
Е
|
D
|
СА граф M′ жетіспеу күйі 3.2. суретте көрсетілген.
Суретте СА граф M′ жетіспеу күйі көрсетілген
Достарыңызбен бөлісу: |