Πεπερασμένα αυτόματα

Το θεωρητικό μοντέλο για την αναγνώριση μιας γλώσσας είναι ένα αυτόματο (automaton). Δύο αυτόματα τα οποία θα εξετάσουμε είναι τα:

Τα πεπερασμένα αυτόματα ορίζονται από την πεντάδα Μ = (Κ, Σ, δ, S, F):

K: Πεπερασμένο σύνολο καταστάσεων
Σ: Πεπερασμένο αλφάβητο εισόδου
δ: συνάρτηση αλλαγής κατάστασης (transition function) από μια κατάσταση Χ σε μια Χ' με βάση ένα σύμβολο εισόδου σ. δ(Χ, σ) = Χ'
S: Αρχική κατάσταση
F: Σύνολο τελικών καταστάσεων

Αν η συνάρτηση δ είναι μονότιμη τότε το αυτόματο αυτόματο καλείται ντετερμινιστικό πεπερασμένο αυτόματο (ΝΠΑ) (deterministic finite automaton (DFA)). Αντίθετα, αν για κάποιες τιμές (Χ, σ) της δ υπάρχουν πολλές πιθανές νέες καταστάσεις X' τότε το αυτόματο καλείται μη ντετερμινιστικό πεπερασμένο αυτόματο (ΜΠΑ) (non-deterministic finite automaton (NFA)). Οι γλώσσες που αναγνωρίζονται από τα πεπερασμένα αυτόματα λέγονται κανονικές γλώσσες (regular languages). Οι γλώσσες αυτές είναι κατάλληλες για να περιγράψουν τις λεκτικές μονάδες ενός προγράμματος.

Ένα πεπερασμένο αυτόματο μπορεί να παρασταθεί ως: