Detta dokument beskriver en metod för att konstruera en minimal deterministisk ändlig automaton (DFA) från ett reguljärt uttryck. Det är baserat på en uppsättning graf grammatik regler för att kombinera många grafer (DFA) för att få en annan önskad graf (DFA). Grafens grammatikregler presenteras i form av en tolkningsalgoritm som omvandlar ett reguljärt uttryck R till en minimal deterministisk finit automaton M sådan att det språk som accepteras av DFA M är samma som det språk som beskrivs av reguljärt uttryck R. Den föreslagna algoritmen tar bort beroendet över nödvändigheten av lång kedja av konvertering, det vill säga reguljärt uttryck → NFA med ε-transitioner → NFA utan ε-transitioner → DFA → minimal DFA. Därför är den största fördelen med vår minimala DFA-konstruktionsalgoritm dess minimala mellanliggande minneskrav och därmed den minskade tids komplexiteten. Den föreslagna algoritmen konverterar ett reguljärt uttryck av storlek n till dess minimala motsvarande DFA i O (n.log 2 n) tid. Utöver ovanstående förkortas tids komplexiteten ytterligare till O(n.log e n) för n ≥ 75.
Sanjay Bhargava, etc. REF beskrev en metod för att konstruera en minimal deterministisk finit automaton (DFA) från ett reguljärt uttryck.
Construction of a Minimal Deterministic Finite Automaton from a Regular Expression
{'venue': None, 'journal': 'International Journal of Computer Applications', 'mag_field_of_study': ['Computer Science']}