„Determinisztikus véges állapotú gép” változatai közötti eltérés
| [nem ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Visszaállítottam a lap korábbi változatát: 89.251.35.206 (vita) szerkesztéséről Luckas-bot szerkesztésére |
|||
61. sor:
A DFA az egyik leggyakorlatiasabb modell a számítógép-tudományban, mert végrehajtási ideje lineárisan függ a bemenő string hosszától, álladó a helyigénye, ha egy [[online algoritmus]]sal szimulálják a DFA-t. Adott két DFA-ra létezik olyan hatékony algoritmus, amely képes az álatala felismert nyelvben felismerni az [[unió (halmazelmélet)|unió]], a [[komplementerképzés]] és a [[különbségképzés]] műveleteket. Léteznek hatékony algoritmusok annak meghatározására, hogy egy DFA felismer egy stringet, egy DFA felismer minden stringet vagy mindkét DFA felismeri ugyanazt a nyelvet, és lehet olyan DFA-t találni, amely egy adott nyelvet minimális számú állapottal ismert fel. Ez az úgynevezett [[minimálautomata]].
Más oldalról a DFA-k erősen korlátozott teljesítményt nyújtanak az általuk felismert nyelvekben, valamint nem alkalmasak olyan problémák megoldására, amelyekhez emlékezetre van szükség.
== Források ==
| |||