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 (formal, wy kinne der fan útstelle 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 sema's, fan praktyske 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:

De problemen fan ien fan 'e twa resultaten fan ûnôfhinklike en net kompatibele eveneminten is lyk oan' e bedoeling fan har kâns.

Foarbyld 4.6

Besykje fragen en taken

Struktureelteorem

Value formalisaasje

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

2019 @ bibinar.info