Мили автоматы
Мили автоматы өтпелі кесте және кесте арқылы анықтау арқылы шығаруға болады.
Өтпелі кестеде AA Мили am бағанының және zf жолының қиылысында күй деп жазылады, ол am және zf функциясының δ функциясы болып табылады.
Шығару кестесінде AA Мили am бағанының және zf жолының қиылысында шығыс сигналы жазылады, ол am және zf-тен λ функциясы болып табылады.
Мысал: Mealy машинасының тапсырмасын кесте түрінде қарастырыңыз (машинаның екі кірісі, екі шығысы және үшеуі бар мемлекеттер).
Мили машинасын анықтаудың графикалық жолы
График – түзулер арқылы қосылған төбелердің жиыны ал шыңдар арасындағы қашықтық бізді қызықтырмайды. Егер жолдар көрсеткілер, онда онсыз график бағытталған (направленным) деп аталады атқыш - бағдарсыз.
Суретте 3 күйдегі Мили автоматының графигі көрсетілген 2 кіріс және 2 шығыс (алдыңғы мысалды қараңыз).
Мили алгоритмі (баламалы күй алгоритмі)
а) K =< A ,Q , B ,δ ,λ > автоматы берілсін және оның күйлерінің саны n =| Q | .
b) { } (0) эквиваленттік кластарының бастапқы жуықтауын анықтаңыз.
және біз бұны келесідей орындаймыз: екі күй q және ' q бір эквиваленттік класқа тағайындалған егер барлық кіріс белгілері үшін болса ғана.
с) i қадамда эквиваленттік кластарға бөлуді алайық
онда i +1 қадамында бірдей эквиваленттік кластағы екі q және ' q күйі
бір сыныпқа сілтеме егер әйтпесе түземіз
жаңа сынып мұнда q күйін және ол үшін барлық басқа '' q күйлерін қоямыз
d) Егер бұл қадам сыныптарға бөлуді өзгертпесе, әйтпесе k қадамында процедураны аяқтаймыз
қайталау в).
Ескерту: Меали алгоритмі конструктивті, өйткені қадамдар саны ең көбі n-1. Авторы Конструкция бір жиынтықтан күйді ажыратуға болмайтынын көрсетеді.
Мысалы: К күй машинасы автомат кестесі ретінде берілген
Біз бастапқы жуықтауды орнаттық:
0. {q1, q4, q6, q9} {q2, q3, q8} {q5, q7}
1-қадам: біз бір сыныпқа екі күйді тағайындаймыз (алуым бойынша)
1. {q1, q4, q6} {q9} {q2, q3, q8} {q5, q7}
2. {q1, q4} {q6} {q9} {q2, q3, q8} {q5, q7}
3. {q1, q4} {q6} {q9} {q2, q3, q8 } {q5, q7 }
Сыныптарға бөліну өзгермегендіктен, минимумда деп қорытынды жасауға болады машинаның 6 күйі болады – бұл С1, С2, С3, С4, С5, С6
Достарыңызбен бөлісу: |
