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

Пример 9.5

Да предположим, че има състояние, посочено от таблицата:

Въз основа на това ще създадем друга таблица, клетките от която ще съответстват на всички различни двойки q i q j ( ij), като я попълват съгласно следните правила:

· Ако двете състояния q i и q j са нееквивалентни (т.е. за всяка стойност на входния символ х , изходните стойности са различни), тогава съответната клетка се зачертава;

· Ако в състоянията q i и q j за всеки x , изходните стойности са еднакви, тогава всички двойки състояния q v q w ( vw), различни от q i q j , се записват в клетките, в които машината може да премине от qi и q j при подаване на същия входен символ.

Според първото правило, например, клетката, съответстваща на двойката q 1 q 2, се оказва зачертана, тъй като при x = 0 се извеждат различни стойности (1 и 0). Съгласно второто правило, например за чифт q5 q6 , трябва да напишете чифт q2 q 5 от следните съображения: за q 5 и q 6 всички изходни символи са еднакви за идентичен вход; х = 0 води до първоначалната двойка q5 q 6 ; x = 1 води до двойка идентични състояния q 6 q 6 .

Други комбинации се анализират по същия начин.

Накрая, чрез последващи трансформации, клетките се закръгляват, в които има двойки, които съответстват на клетките, които вече са зачеркнати. Например, трябва да пресечете клетката за двойката q 1 q 4 , тъй като тя съдържа q 3 q 6 , а също и q 3 q 4 , защото тя има q 2 q 3 . След това отново трябва да пресечете всички клетки, които съдържат двойки, които съответстват на изрязаните клетки. Процедурата трябва да продължи, докато се формира таблица, в която не могат да бъдат зачертани останалите клетки. За разглеждания пример, тези клетки са подчертани с удебелен шрифт. Може да се докаже, че останалите неотрязани клетки съответстват на всички двойки еквивалентни състояния. Това са q 1 q 3 , q 2 q 5 , q 2 q 6 и q 5 q 6 . Класовете еквивалентност се формират от състояния, които са двойно еквивалентни. В този случай те са { q 1 , q 3 } и { q 2 , q 5 , q 6 }. Държавите, които не са включени в тези класове, са еквивалентни само на себе си и формират свои собствени класове еквивалентност; в този пример е { q 4 }. По този начин бяха разграничени класовете за еквивалентност.

След идентифициране на класовете еквивалентност на състоянията за автомата М, можем да конструираме еквивалентен автомат М '. Като входна и изходна азбука за M ', ние вземаме съответните азбуки M и сравняваме всеки клас еквивалентни състояния M с едно състояние M'. За горния пример можем да вземем ( q 1 ) '↔ { q 1 , q 3 }, ( q 2 )' ↔ { q 2 , q 5 , q 6 } , ( q 3 ) ' ↔ {q 4 }.

Накрая получаваме таблицата на новия автомат M '.

Следната теорема може да бъде доказана *:

* Тези, които се интересуват от доказателства, могат да бъдат адресирани до книгата LA Шоломов [48, стр.125-126].





Вижте също:

Тестови въпроси и задачи

Паралелен канал за предаване

Пример 7.11

Ентропийни свойства

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

2019 @ ailback.ru