Ako rozlišovať medzi DFA a NDFA

Deterministické a nedeterministickej konečné automaty sú dva typy koncepčných " stroje " , ktorých účelom je overiť , či daný reťazec symbolov sa riadi určité pravidlá - ak je to prijateľné , pretože správy v nejakom jazyku alebo kód . Automaty prečíta jeden symbol v čase , a vždy existuje v určitom stave " . " Každý štát automaty môžu byť má sadu pravidiel pre reakciu na ďalší symbol je potrebné čítať - to sa môže zmeniť do iného určitého štátu , alebo zostávajú rovnaké . Ak sa po celý reťazec bol čítal , automaty vstúpil jeden z množiny prijateľných " konečných stavov , " reťazec je gramaticky prijateľné v rámci jazyka automaty testuje pre . Pokyny
1

Skontrolujte pravidlá automatoch je . Patria medzi ne : všetky možných stavov automatoch , jeho súborom konečných stavov a účinky všetkých možných symbol na každého štátu
2

Skontrolujte , či sa niektorý zo štátov v automate majú celý rad možných reakcií na . konkrétny symbol . Ak sa ktorýkoľvek robiť , automaty je non - deterministický - NDFA . Napríklad , ak je počiatočný stav účtovné automaty môžu reagovať na symbol " A " , a to buď tým , že pohybuje na druhom štáte , alebo tým , že zostane rovnaká , je NDFA . NDFA vráti pozitívny výsledok , ak existuje nejaký spôsob , ako dosiahnuť konečného stavu pomocou zadaný reťazec .
3

Majte na pamäti , že DFA existuje pre každú NDFA . Vzhľadom k tomu , NDFA vracia pozitívny výsledok pre určitú reťazec musí mať aspoň jednu úspešnú cestu cez neho pre tento reťazec , musí nutne byť zodpovedajúce DFA , že bude akceptovať , že reťazec , ktorý obsahuje iba pravidlá pre jedinej ceste , ktorá bola použitá . Tu je veľmi jednoduchý príklad : Predpokladajme , že máte NDFA s konečným stavom názvom S1 , ktorého počiatočný stav S0 reaguje na symbol " A " , a to buď zmenou S1 alebo tým , že zostane v S0 . Tento stroj by akceptovať reťazec skladajúci sa iba z " A " , pretože tam je možná cesta k S1 a tam je zodpovedajúca DFA , v ktorej " A " vždy zmení S1 do S0 , výdaj s nevyužitú cestou
.

• Predchádzajúca strana: Ako získať Service Web Raw Data 
• Ďalšia strana: Definícia perzistentných atrament