deterministische en niet- deterministische eindige automaten zijn twee soorten van conceptuele " machines " ontworpen om te controleren of een bepaalde reeks symbolen steunmaatregelen aan bepaalde regels - al is het aanvaardbaar als een boodschap in een aantal talen of code . De automaten leest een symbool op het scherm , en bestaat altijd een bepaalde "state . " Elke staat een automaten kan in een set regels voor het reageren op het volgende symbool te lezen - het kan naar een andere bepaalde toestand of gelijk blijven . Indien , na een hele reeks is gelezen , is de automaten een van een reeks van acceptabele getreden " finale staten , " de string is grammaticaal aanvaardbaar is binnen de taal van de automaten is het testen voor . Instructies
1 Bestudeer de regels van de automaten 's . Deze omvatten : . Alle automaten de mogelijke toestanden , de set van de finale toestanden en de effecten van alle mogelijke symbool op elke staat
controleren 2 te zien of een van de staten van de automaten hebben meerdere mogelijke reacties op een bepaald symbool . Eventuele doet , de automaten is niet- deterministisch - een NDFA . Bijvoorbeeld , wanneer een automaten 's begintoestand kan reageren op het symbool " A " hetzij door te verhuizen naar een tweede toestand of door hetzelfde blijft , is het een NDFA . Een NDFA geeft een positief resultaat als er een manier is om een uiteindelijke toestand met behulp van een gegeven string te bereiken .
3 Houd in gedachten dat een DFA bestaat voor elke NDFA . Omdat een NDFA terugsturen van een positief resultaat op een specifieke string tenminste een succesvolle pad door het voor die string moet hebben , moet er uit noodzaak een overeenkomstige DFA dat die string zal accepteren , met alleen de regels voor de enkel pad dat werd gebruikt . Hier is een heel eenvoudig voorbeeld : Stel je hebt een NDFA met een eindtoestand genaamd S1 , wiens oorspronkelijke staat S0 reageert op het symbool " A " , hetzij door het veranderen naar S1 of door te blijven in S0 . Deze machine zou een tekenreeks die bestaat simpelweg uit te aanvaarden " A , " want er is een mogelijke weg naar S1 , en is er een overeenkomstige DFA waarin " A " verandert altijd S1 tot S0 , de afschaffing van het ongebruikte pad
.
|
