1. 1Жиын ұғымы. Шекті және шексіз жиындар. Жиындарды анықтау тәсілдері.Ішкі жиындар. Берілген жиынның барлық жиынтығы. К- элемент жиындарының саны туралы n- элемент жиынтығы
жүктеу/скачать 336,61 Kb.
|
1. 1Жиын ??ымы. Шекті ж?не шексіз жиындар. Жиындарды аны?тау т?с
| Автоматтардың сипаттамасы
Автоматтың келесі компоненттері бар: 1) сырттан жасалған және зерттелетін жүйенің әрекетіне әсер ететін әсерлер болып табылатын кіріс айнымалылар; 2) осы жүйенің әрекетін сипаттайтын шамалар болып табылатын жүйенің жауабы деп аталатын шығыс айнымалылар. Функционалдылығы жағынан бір-бірінен ерекшеленетін автоматтардың үш мүмкін түрін атап өту қажет. 1. Бірінші типтегі құрылғыларда уақыт мезетінде генерацияланатын шығыс сигналдарының жиыны (G + DO) тек уақыт / уақытында берілген кіріс сигналдарының жиынына ғана тәуелді, ал кірістерінде қабылданған сигналдарға тәуелді емес. алдыңғы уақыттағы автомат.Д интервалы/- автоматтың реакция уақыты.Ол бастапқы/кез келген рұқсат етілген кіріс сигналдар жиындары үшін өзгеріссіз қалады.Осындай бір-бірден және жиынтықтар арасындағы уақыт бойынша өзгеріссіз сәйкестік. кіріс және шығыс сигналдары автоматтардың ішкі күйінің инварианттылығына және осы күйдің сыртқы әсерден тәуелсіздігіне байланысты.Осы типтегі құрылғылар жадысыз автоматтар деп аталады. 2. Екінші типті автоматтарда белгілі бір дискретті уақыт моментінде түзілетін шығыс сигналдарының жиыны тек бір уақыт моментінде берілген сигналдарға ғана емес, сонымен бірге бұрын келген сигналдарға да байланысты. Бұл алдыңғы сыртқы әсерлер автоматта оның ішкі күйін өзгерту арқылы бекітіледі. Осылайша, бұл автоматтың реакциясы кіріс сигналдарының қабылданған жиынтығымен және оның берілген уақыттағы ішкі күйімен бірегей түрде анықталады. Дәл осындай факторлар автоматтың өтетін күйін бірегей түрде анықтайды. 3. Ақырлы автомат – кірістерінің шектеулі саны, ішкі күйлерінің шекті саны бар, жұмысы детерминирленген (ағылшын тілінен – «анық») сипаты бар объект. Егер ақырлы автомат сыртқы жадымен қамтамасыз етілсе және оның шексіз кеңеюіне рұқсат етілсе, онда мұндай жүйе үшінші типтегі автоматтарға жатады, мысалы, Тьюринг машинасы. Ол үшінші типті автоматтардың көмегімен кез келген жүйені модельдеуге болатынын көрсетті, яғни. ақпаратты өңдеудің кез келген алгоритмі жүзеге асырылады. Автомат уақыттың кейбір дискретті моментінде (цикл) жұмыс істейді деп есептейміз. Кіріс сигналы p өзгермейтін уақыт Т арқылы белгіленеді және осы интервалдың ұзақтығын не анықтайтынына байланысты автоматтардың екі класын ажыратамыз: синхронды және асинхронды. Берілген жиындар (P, L, X) және бастапқы ішкі күйі x0 үшін автоматтың жұмысы немесе әрекеті толығымен анықталады және ауысу функцияларымен анықталады. Өтпелі функция келесі уақыт мезетіндегі автоматтың ішкі күйінің кіріс күйіне және қазіргі уақыт мезетіндегі ішкі күйіне тәуелділігін белгілейді. Шығару функциясы автоматтың шығыс күйінің кіріс күйіне және автоматтың ішкі күйіне тәуелділігін белгілейді. Әртүрлі автоматтар үшін бұл тәуелділіктердің әртүрлі сипаты синхронды соңғы детерминирленген автоматтар класындағы автоматтардың жеке түрлерін ажыратуға мүмкіндік береді. Анықтамасы: 1. Ақырлы автоматты бес нысан ретінде көрсетеміз: K =< A, Q, B, δ , λ > - , мұндағы A - кіріс алфавиті A { } a a am , , , = 1 2 K ; Q - күйлердің алфавиті (жиыны) n-ді қамтиды нөлден басталатын элементтер { } 0 1 , , Q = q K qn− ; B - шығыс алфавиті B { } b be , , = 1 K ; δ- ауысулардың салыстырулары (функциясы) δ : Q × A → Q ; λ - шығыстардың салыстырулары (функциясы). λ : Q × A → Q ; Егер басқаша айтылмаса, автоматтың бастапқы күйі q1, ал соңғы күйі q0 болады. Егер δ және λ салыстырулары функция болса, онда автомат детерминирленген, әйтпесе автомат детерминирленген емес.Анықтамасы: 2. Ақырлы автомат толық деп аталады, егер барлық реттелген жұптар үшін i j q a i j i j PK q a → q 'a '∈ түріндегі пәрмен бар. Автоматты бейнелеуден (функция) δ , λбарлық нүктелерде анықталады. Бұл автомат кестесінде бос орындар жоқ дегенді білдіреді. Ұяшықтар, q0 соңғы күйіне сәйкес келетін бағанды қоспағанда. Анықтама: 3. Автоматты салыстыру – кіріс жолдарын көрсететін сәйкестік демалыс күндері мемлекеттік машина. К =< A,Q,B,δ ,λ > шекті автоматы берілсін. Оның енгізуіне жолдардың барлық түрлерін жіберу алфавитінде А , шығысында біз В алфавитіндегі жолдарды аламыз i.e. Ақырлы күй машинасы К А әліпбиінің үстіндегі әмбебап жиынды әмбебап жиынға салыстыру алфавит В. K A → B Егер жол + α ∈ A берілсе, онда ақырлы автоматтың кірісіне беріліп, келесіге әкеледі: шығысында + β ∈ B жолының пайда болуы, ол былай жазылады: K( ) qi ,α . К - біз шақырамыз автоматты оператор. α жолы j j jk a ,a , ,a α = 1 2 K болсын. (j a ) K( ) qi ,α : ()( ) , ( , , ) ) i i jk 1 jk q a q a a δ = δ δ Kδ K − . Автомат операторының индуктивті анықтамасы, яғни. жол ұзындығы болғанда = 1. ( ) ( ) 1 , , i j i j K q a = λ q a ; Қ. ( ) i j jk k K q ,a 1Ka = β ; K+1. ( , ) ( ( , ) ) i j1 jk jk+1 = k i j1 jk jk+1 K q a Ka a β λ δ q a Ka a ; 4.2 жүктеу/скачать 336,61 Kb. Достарыңызбен бөлісу:
|