Erinevus NFA ja DFA vahel

NFA vs DFA

Arvutusteooria on arvutiteaduse haru, mis tegeleb algoritmide abil probleemide lahendamisega. Sellel on kolm haru, nimelt; arvutusliku keerukuse teooria, arvutatavuse teooria ja automatoni teooria.

Automaat ehk automaatteooria on abstraktsete matemaatiliste masinate või süsteemide uurimine, mida saab kasutada arvutusprobleemide lahendamiseks. Automaat koosneb olekutest ja üleminekutest ning kuna see näeb sümbolit või sisendtähte, muudab see teise oleku, võttes sisendiks praeguse oleku ja sümboli..

Automaadil või automatiseeritud teoorial on mitu klassi, mis hõlmavad deterministlikku lõplikku automatismi (DFA) ja mittedeterministlikku lõplikku automaati (NFA). Need kaks klassi on automaadi või automaadi üleminekufunktsioonid.

Üleminekuperioodil ei saa DFA kasutada n tühja stringi ja seda võib mõista kui ühte masinat. Kui string lõpeb olekus, mis pole vastuvõetav, lükkab DFA selle tagasi. DFA-masina saab ehitada iga sisendi ja väljundiga.

DFA-l on tähestiku iga sümboli kohta ainult üks oleku üleminek ja selle üleminekuks on ainult üks lõppseisund, mis tähendab, et iga loetud tähemärgi jaoks on DFA-s üks vastav olek. DFA-sse kuulumist on lihtsam kontrollida, kuid seda on keerulisem üles ehitada. Tagasijõudmine on DFA-s lubatud ja see nõuab rohkem ruumi kui NFA.

Tagasijõudmine pole NFA-s alati lubatud. Kuigi mõnel juhul on see võimalik, siis teistes mitte. NFA ehitamine on lihtsam ja see nõuab ka vähem ruumi, kuid iga sisendi ja väljundi jaoks pole NFA masinat võimalik ehitada..

Selle all mõistetakse mitmeid pisikesi masinaid, mis arvutavad üheaegselt ja liikmesust on raskem kontrollida. See kasutab tühja stringi üleminekut ja iga oleku- ja sisendsümboli paari jaoks on arvukalt võimalikke järgmisi olekuid. See algab kindlast olekust ja loeb sümboleid ning automaat määrab seejärel järgmise oleku, mis sõltub praegusest sisendist ja muudest järgnevatest sündmustest. Nõustuvas olekus aktsepteerib NFA stringi ja lükkab selle teisiti tagasi.

Kokkuvõte:

1. „DFA“ tähistab „deterministlikku lõplikku automaati“ ja „NFA“ tähistab „mittedeterministlikku lõplikku automaati“.
2.Mõlemad on automattide üleminekufunktsioonid. DFA-s on järgmine võimalik olek selgelt eristatav, samas kui NFA-s saab igal oleku- ja sisendsümboli paaril olla palju järgmisi olekuid.
3.NFA saab kasutada tühja stringi üleminekut, samal ajal kui DFA ei saa kasutada tühja stringi üleminekut.
4.NFA on lihtsam ehitada, samas kui DFA ehitamine on raskem.
5.Tagasi jälgimine on DFA-s lubatud, samas kui NFA-s võib see olla lubatud või mitte.
6.DFA nõuab rohkem ruumi, samas kui NFA nõuab vähem ruumi.
7.Kuigi DFA-d võib mõista ühe masina ja DFA-masina saab konstrueerida iga sisendi ja väljundi jaoks, 8.NFA-d võib mõista mitme väikese arvutis, mis arvutavad koos, ja puudub võimalus ehitada NFA-masin iga sisendi jaoks ja väljund.