border=0

Foarbyld 9.5

Tink derom dat in steatermasine oanjûn is troch de tabel:

Op grûn dêrfan sille wy in oar tabel meitsje, de sellen dy't oerienkomme mei alle ferskate pairs q i q j ( ij), filling it neffens de folgjende regels:

As de twa lannen q i en q j nonequivalent binne (dus, foar elke wearde fan it ynputsymbol x , de útfieringswearden binne ferskillend), dan wurdt de oerienkommende sel feroare;

As yn 'e steaten q i en q j foar elk x de útfieringswearden binne deselde, dan binne alle paragrafen fan staaten q v q w ( vw), oars as q i q j , wurde skreaun nei de sellen, yn wêr de masine kin fan q i en q j by it ynstellen fan deselde ynfier karakter.

Neffens de earste regel, bygelyks, is de sel as korrespondearjend mei it pear q 1 q 2 útskreaun, om't x = 0 binne ferskillende wearden útfierd (1 en 0). Neffens de twadde regel, bygelyks, foar in pear q 5 q 6, moatte jo in pear q 2 q 5 fan 'e folgjende oerwizen skriuwe: foar q 5 en q 6 binne alle útfiersymboalen deselde foar deselde ynput; x = 0 liedt nei it orizjinele pear q 5 q 6 ; x = 1 liedt ta in pear identike steaten q 6 q 6 .

Oare kombinaasjes wurde op deselde wize analysearre.

Uteinlik folgje de transformaasje de sellen wêrtroch't pearen binne dy't oerienkomme mei de sellen dy't al fuort binne. Bygelyks, moatte jo de sel foar it paar q 1 q 4 útfiere, om't it q 3 q 6 befettet, en ek q 3 q 4 , om't it q 2 q 3 hat . Dêrnei moatte jo alle sellen útfiere dy't pearen befetsje dy't oerienkomme mei selektearre sellen. De proseduere moat trochgean, oant in tafel foarme wurdt, wêryn gjin oerbleaune sellen útgean kinne. Foar it beskôgjende foarbyld binne dizze sellen yn fett markearre. It kin bewiisd wurde dat de oerbleaune ûnkropbere sellen alle pasen fan lykweardige steaten befetsje. Dit binne q 1 q 3 , q 2 q 5 , q 2 q 6 en q 5 q 6 . Ekkwaliteitsklassen foarmje foarme troch steaten dy't paarlik lykweardich binne. Yn dit gefal binne dit { q 1 , q 3 } en { q 2 , q 5 , q 6 }. Steaten dy't net yn dizze lessen binne opnommen binne allinich foar harsels en foarmje har eigen lykwichtensklassen; yn dit foarbyld is it { q 4 }. Sa waarden lykwols lykwols ûnderskieden.

Nei it identifisearjen fan de lykweardigens fan steaten foar de automaton M, kinne wy ​​in autentyk automaat M 'oanbiede. As de ynput- en útfier-alfabetten foar M 'n, nimme wy de oerienkommende alfabetten M, en foar elke klasse fan lykweardige steaten M fergelykje ien steat M'. Foar it boppeneamde foarbyld kinne wy ​​nimme ( q 1 ) '↔ { q 1 , q 3 }, ( q 2 )' ↔ { q 2 , q 5 , q 6 } , ( q 3 ) ' ↔ {q 4 }.

Uteinlik krije wy de tafel fan 'e nije automaton M'.

It folgjende teorem kin bepaald wurde *:

* Wa't ynteressearre is foar bewiis kin oanpast wurde oan it boek LA Sholomov [48, pp.125-126].





Sjoch ek:

Uniforme alfabetyske binêre kodearring. Byte koade

Glossar

Oerstap fan fraksjoneel nûmers fan ien nûmersystem nei in oar

Foarbyld 4.16

Foarbyld 4.9

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ bibinar.info