Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Еквивалентни автомати

Автоматичните машини са устройства за обработка на дискретна информация. Естеството на обработваната информация определя входните и изходните азбуки (X и Y ); азбуката на вътрешните състояния ( Q ) се определя от структурата на автомата и, общо взето, тя може да се различава от различните автомати с еднакви входни и изходни азбуки. Следователно, едно и също преобразуване на информация може да се извърши от автомати с различен брой състояния и следователно чрез различен брой команди. Въвеждаме няколко определения:

Състоянията q на автомата M и q 'на автомата M' се считат за еквивалентни, ако и двата автомата, получили една и съща (всяка) входна последователност от символи, го обработват в една и съща изходна последователност.

Автоматите М и М 'се наричат еквивалентни, ако за всяко състояние на автомата М съществува еквивалентно състояние на автомата М' и обратно.

С други думи, еквивалентните автомати изпълняват същите трансформации, но могат да имат различен брой вътрешни състояния.

Концепцията за еквивалентност на състоянията се прилага за един автомат (формално можем да приемем, че M и M 'са еднакви). За един автомат, различни състояния ще бъдат еквивалентни, чрез които една и съща входна последователност от символи се преобразува в един и същ изход.

Във връзка със синтеза на схеми, от практически интерес е проблемът за конструирането на автомат, който изпълнява даден набор от трансформации с минималния брой вътрешни състояния.

Автомат, еквивалентен на даден и имащ най-малкия от всички възможни състояния, се нарича минимален.

Задачата за изграждане на минимален автомат се нарича минимизиращ проблем на автомат. Решението му се извършва на два етапа: първо се установяват всички нееквивалентни състояния на началния автомат, след което се поставя минималният автомат. На свой ред, за да се определят не еквивалентни състояния, е необходимо да се идентифицират класове еквивалентни състояния.

Да предположим, че има автомат с набор от вътрешни състояния Q , сред които може да има еквивалент. Отношенията на еквивалентност на състоянието имат обичайните еквивалентни свойства, т.е. рефлексивност, симетрия и транзитивност. Следователно, множеството Q може да бъде разделено на класове еквивалентност. Разгледайте процедурата чрез пример.

Вижте също:

А.2. Добавяне и умножение на вероятностите

Пример 2.8

Пример 9.1

Пример 2.5

Пример 4.1

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru