Lõpliku automaadi animaator

Lõplikul automaadil on fikseeritud mälu — tema olekute hulk. Ükskõik kui pikk on sisendstring, ei kasuta masin kunagi rohkem mälu kui tal on olekuid. Seetõttu ei saa DFA-d piiramatult loendada: pole olekut, mis 'mäletaks' suvalist täisarvu. Pumbalemma teeb selle täpseks: iga piisavalt pika DFA poolt aktsepteeritud stringi keskmist osa saab suvaliselt palju kordi korrata ja string jääb ikka aktsepteerituks. Keeled, mida ei saa pumbata (nagu aⁿbⁿ, võrdne arv a-sid ja b-sid), vajavad pinuautomaati või Turingi masinat. Myhill-Nerode teoreem annab täpse miinimumi: olekute arv võrdub sisendi prefiksite eristatavate ekvivalentsiklasside arvuga.

Deterministlik lõplik automaat on lihtsalt sildistatud diagramm olekutest, mida ühendavad nooled. Iga oleku ja iga sisendsümboli jaoks on täpselt üks nool, mida järgida — seega pole kunagi valikut. Masin loeb sõne ühe korra vasakult paremale ja jõuab ühte ainsasse olekusse. Kui see lõppolek on märgitud aktsepteerivaks, kuulub sisend keelde. Selle jälgimine on sama lihtne kui märgi lükkamine mööda nooli — just seda see tööriist näitabki.

Lõplikud automaadid ei alguse arvutiteadusest. 1943. aastal kirjeldasid Warren McCulloch ja Walter Pitts neuroneid kui lihtsaid sisse/välja lülituvaid üksusi, mis on omavahel ühendatud, ja sellest sai esimene lõpliku olekumasina matemaatiline mudel. 1951. aastal analüüsis Stephen Kleene, milliseid mustreid sellised 'närvivõrgud' ära tunda suudavad, ja nimetas need regulaarseteks sündmusteks — tänapäeva regulaaravaldiste alge. Nii et automaat, mida sa siin sammhaaval läbid, pärineb otse katsest selgitada, kuidas aju arvutab.