Θεωρία αυτομάτων

Στη Θεωρητική πληροφορική, θεωρία αυτομάτων είναι η μελέτη των μαθηματικών αντικειμένων που ονομάζονται αφηρημένες μηχανές ή αυτόματα και των υπολογιστικών προβλημάτων που μπορούν να λυθούν με αυτά.

Παράδειγμα αυτόματου. Η μελέτη των μαθηματικών ιδιοτήτων τέτοιων αυτομάτων είναι η Θεωρία αυτομάτων.

Το σχήμα δεξιά παρουσιάζει μια μηχανή πεπερασμένων καταστάσεων, η οποία ανήκει σε μια γνωστή κατηγορία αυτομάτων. Το αυτόματο αυτό αποτελείται από καταστάσεις (που απεικονίζονται με κύκλους), και μεταβάσεις (που απεικονίζονται με βέλη). Καθώς το αυτόματο βλέπει ένα σύμβολο εισόδου, εκτελεί μια μετάβαση (ή πήδημα) σε άλλη κατάσταση, ανάλογα με τη συνάρτηση μετάβασης (η οποία δέχεται την τρέχουσα κατάσταση και το τελευταίο σύμβολο ως εισόδους).

Η θεωρία αυτομάτων είναι πολύ σχετική με τη θεωρία τυπικών γλωσσών. Ένα αυτόματο είναι η πεπερασμένη περιγραφή μιας τυπικής γλώσσας, η οποία μπορεί να είναι άπειρο σύνολο. Τα αυτόματα συνήθως κατηγοριοποιούνται ανάλογα με το είδος της τυπικής γλώσσας που αναγνωρίζουν.

Τα αυτόματα παίζουν σημαντικό ρόλο στη θεωρία υπολογισμού, τη σχεδίαση μεταγλωττιστών, και την τυπική επαλήθευση.