border=0

Equivalent Automata

Automatyske masines binne apparaten foar it ferwurkjen fan diskrete ynformaasje. De natuer fan 'e ynformaasje dy't ferwurke wurdt bepaalt de ynfier- en útfierbere alfabetten (X en Y ); It alfabet fan ynterne steaten ( Q ) wurdt bepaald troch de struktuer fan de automaton en, yn oerienstimming mei, kin it ferskille fan ferskillende automaten mei deselde ynfier- en útfier-alfabetten. Dêrtroch kin deselde ynformaasjeferbinings troch automaten útfierd wurde mei in ferskillende tal steaten en, dêrom, troch in oar oantal kommando's. Wy prate in oantal definysjes yn:

De staten q fan 'e automaton M en q' fan 'e automaton M' wurde beskôge as equivalent as beide automaten, dy't itselde (ien) yntekening fan karakters krigen hawwe, ferwurke it yn deselde útfier sekere.

De automaten M en M 'wurde lykweardich neamd as foar elke steat fan' e automaton M besteane in lykweardige steat fan 'e automaton M' en oarsom.

Mei oare wurden, lykweardige automaten realisearje deselde transformaasje, mar kinne in oare tal ynterne steaten hawwe.

It begryp fan lykwichtens fan steaten is jildich foar ien automaton (formelje kinne wy ​​ferwize dat M en M 'itselde binne). Foar ien automaton sille ferskate staaten lykweardich wurde, troch hokker deselde yngongsferskes fan karakters omdield yn deselde útfier.

Yn ferbân mei de synteze fan regelingen is praktysk be>

In automaton, lykweardich oan in opjûne manier en it lytste fan alle mooglike nûmer fan steat wurdt minimal neamd .

De opdracht om in minimalautomat te bouwen wurdt it minimalisearringsprobleem fan in automaton neamd. De oplossing is yn twa stappen útfierd: earst wurde alle net-folsleinste steaten fan 'e earste automaat ynsteld, en dan wurdt de minimale automaton bepaald troch har. Op it lêst, om net-lykweardige steaten te bepalen, is it nedich om klassen fan lykweardige steaten te identifisearjen.

Tink derom dat der in automaton is mei in ynset fan ynterne steaten Q , dêr't ûnder oaren it lykweardich wêze kinne. Steatlike lykweardigensrelaasjes hawwe de gebrûklike lykweardich eigenskippen, d. reflexiviteit, symmetry en transitiviteit. Dêrom kin de set Q yndield wurde yn lykweardigensklassen. Besykje de prosedure by foarbyld.

Sjoch ek:

Entropy as mjit fan wissichheid

Soft-definition algoritme

Begjin definieare

Foarbyld 10.1

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

2019 @ edudocs.fun