1. 1Жиын ұғымы. Шекті және шексіз жиындар. Жиындарды анықтау тәсілдері.Ішкі жиындар. Берілген жиынның барлық жиынтығы. К- элемент жиындарының саны туралы n- элемент жиынтығы
жүктеу/скачать 336,61 Kb.
|
| Тану автоматтары
Автоматты тану құралдары Автомат-трансформаторларды қарастырғаннан кейін соңғы автоматтардың екінші кең тараған түрін – автоматтарды танушыларды зерттеуге көшейік. Олардың автоматты түрлендіргіштерден айырмашылығы, шығыстар мен ауысулардың функциялары кіріс сигналдарына тәуелді емес және күйлердің бір орындық функциялары болып табылады. Жалпы жағдайда автоматты танушы келесі қадамда қалай әрекет ету керектігін нақты көрсетпейді, бірақ есептеу процесін бірнеше жолмен жалғастыруға мүмкіндік береді. Сондықтан, барлық соңғы автоматтарды танғыштар практикалық қолдану үшін қолайлы танғыштарды құруға жарамайды. Бұл кемшілік детерминирленген автоматтарда жоқ (детерминирленген емес автоматтардың ерекше жағдайы). Детерминирленген емес автоматтар-танғыштар Ақырлы автомат (ақырлы автомат, ақырлы күй машинасы) – бес ақырлы жиын R=(A, Q, , I, F), мұндағы A – осы автоматтың кіріс алфавиті, Q – автомат күйлерінің жиыны, , жиынтық бастапқы күйлер, соңғы немесе қабылдаушы (соңғы, қабылдаушы) күйлердің жиынтығы. Егер болса, онда п-дан q-ға көшу деп аталады, ал х сөзі осы ауысудың белгісі болып табылады. Ақырлы автоматтарды танғыштарды күй диаграммалары (күй диаграммасы) ретінде бейнелеуге болады (кейде олар өтпелі диаграммалар (өтпелі диаграмма) деп аталады) - бұл ақырлы автоматтарды түрлендіргіштерге арналған Мур диаграммаларының аналогы. Анықтама1 Күй машинасын танушыға арналған ауысу диаграммасы бағытталған көп түбірлі псевдограф болып табылады (а) шыңдар жиыны Q жиынымен сәйкес келеді және әрбір бастапқы күй оған апаратын қысқа көрсеткі арқылы танылады және әрбір қабылдаушы күй диаграммада қос шеңбермен белгіленеді; (b) оның p-тен q-ға дейінгі доғалары (pQ, qQ) xA* сөзімен белгіленеді және осылайша олар осы автоматтың ауысуларына сәйкес келеді. Ескерту. Егер танушыда ортақ басы және ортақ соңы бар бірнеше ауысулар болса, онда мұндай ауысулар параллель деп аталады. Күй диаграммасында олар бірнеше жиектерге сәйкес келеді, сондықтан олар кейде бір доға ретінде бейнеленген. Бұл жағдайда ауысулардың белгілері үтірмен бөлінген. Толық ақырлы автомат Егер кейбір оқиғалардың әсерінен танушы автоматта ауысулар анықталмаса, онда бұл сәйкес енгізу тілінің тізбектерінің қате екенін білдіреді, оларға рұқсат етілмейді, олар осы автомат таныған тілге жатпайды. Автоматпен кез келген манипуляциялар үшін бұл күй анық түрде енгізілуі керек. Алынған толық автомат тілді тану тұрғысынан бастапқы автоматқа тең. Ақырлы автоматтарды танушылардың минимизациясы Берілген автомат тілін танитын бірегей (изоморфизмге дейін, яғни күй атауына дейін) минималды соңғы автомат бар. КА өзінің канондық көрінісіне ие - бұл минималды КА. жүктеу/скачать 336,61 Kb. Достарыңызбен бөлісу:
|