1. Электр сигналдарының спектрлік анализінің негіздері
жүктеу/скачать 430,55 Kb.
|
емтихан жауаптары (1)
| Автоматтар теориясы
1. Детерминирленген ақырлы күй машинасының тұжырымдамасын сипаттаңыз. Мысал келтіріңіз. Детерминирленген ақырлы күй машинасы белгілі бір күйлер тізбегінен өту арқылы берілген жол таңбаларын қабылдайтын немесе қабылдамайтын соңғы күй машинасы болып табылады. МакКаллок пен Уолтер Питтс 1943 жылы мемлекеттік машинаға ұқсас тұжырымдаманы ұсынған алғашқы зерттеушілердің бірі болды. Үшке бөлінетін екілік сандарды ғана қабылдайтын детерминирленген күй машинасының мысалы. Сурет күй диаграммасы арқылы детерминирленген күй машинасын көрсетеді. Бұл мысалда үш күй бар - S0, S1 және S2 (суретте шеңберлер арқылы көрсетілген). Автомат нөлдер мен бірліктердің соңғы тізбегін кіріс ретінде қабылдайды. Әрбір күй үшін 0 және 1 үшін күйден күйге апаратын өтпелі көрсеткі бар. Таңбаны оқығаннан кейін DFA өту көрсеткісінен кейін бір күйден екінші күйге детерминирленген түрде ауысады. Мысалы, егер автомат S0 күйінде болса және кіріс белгісі 1 болса, онда автомат детерминирленген түрде S1 күйіне өтеді. DFA-да есептеу басталған жерден бастапқы күй (графикалық түрде жоқ жерден көрсеткі арқылы көрсетілген) және есептеудің сәтті болатынын анықтайтын соңғы күйлер жинағы (графикалық түрде қосарланған шеңбер ретінде көрсетілген) болады. 2. Детерминирленбеген ақырғы күй машинасының тұжырымдамасын сипаттаңыз. Мысал келтіріңіз. Детерминирленбеген ақырлы күй машинасы - бұл келесі шарттарды орындамайтын детерминирленген соңғы автомат: оның кез келген ауысуы ағымдағы күймен және кіріс белгісімен бірегей түрде анықталады; әрбір күй өзгерісі үшін кіріс таңбасын оқу қажет. DFA - Детерминирленген ақырлы күй машинасы NFA - Детерминирленбеген ақырғы күй машинасы Ішкі жиынды құру алгоритмін[en] пайдаланып, кез келген Детерминирленбеген ақырғы күй машинасы эквивалентті DFA-ға, яғни бірдей ресми тілді танитын DFA-ға түрлендіруге болады[1]. DFA сияқты, NFA тек қарапайым тілдерді таниды. NFA-ны 1959 жылы Майкл О. Рабин мен Дана Скотт ұсынған, олар оны DFA-ға баламалы екенін көрсетті. NFA тұрақты өрнектерді жүзеге асыруда пайдаланылады - Томпсон конструкциясы - жолдар үлгісін тиімді тани алатын тұрақты өрнекті NFA-ға түрлендіру алгоритмі. Керісінше, Kleene[en] алгоритмі NFA-ны өлшемі әдетте автоматтың өлшеміне экспоненциалды түрде тәуелді тұрақты өрнекке түрлендіру үшін пайдаланылуы мүмкін. жүктеу/скачать 430,55 Kb. Достарыңызбен бөлісу:
|