Θεωρία αυτομάτων
 |
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Στη Θεωρητική πληροφορική, θεωρία αυτομάτων είναι η μελέτη των μαθηματικών αντικειμένων που ονομάζονται αφηρημένες μηχανές ή αυτόματα και των υπολογιστικών προβλημάτων που μπορούν να λυθούν με αυτά.
Το σχήμα δεξιά παρουσιάζει μια μηχανή πεπερασμένων καταστάσεων, η οποία ανήκει σε μια γνωστή κατηγορία αυτομάτων. Το αυτόματο αυτό αποτελείται από καταστάσεις (που απεικονίζονται με κύκλους), και μεταβάσεις (που απεικονίζονται με βέλη). Καθώς το αυτόματο βλέπει ένα σύμβολο εισόδου, εκτελεί μια μετάβαση (ή πήδημα) σε άλλη κατάσταση, ανάλογα με τη συνάρτηση μετάβασης (η οποία δέχεται την τρέχουσα κατάσταση και το τελευταίο σύμβολο ως εισόδους).
Η θεωρία αυτομάτων είναι πολύ σχετική με τη θεωρία τυπικών γλωσσών. Ένα αυτόματο είναι η πεπερασμένη περιγραφή μιας τυπικής γλώσσας, η οποία μπορεί να είναι άπειρο σύνολο. Τα αυτόματα συνήθως κατηγοριοποιούνται ανάλογα με το είδος της τυπικής γλώσσας που αναγνωρίζουν.
Τα αυτόματα παίζουν σημαντικό ρόλο στη θεωρία υπολογισμού, τη σχεδίαση μεταγλωττιστών, και την τυπική επαλήθευση.
Θεωρία αυτομάτων
[Επεξεργασία | επεξεργασία κώδικα]Η θεωρία αυτομάτων είναι το πεδίο που μελετά τις ιδιότητες διαφόρων τύπων αυτομάτων. Για παράδειγμα, η ακόλουθες ερωτήσεις μελετώνται για κάθε τύπο αυτομάτων.
- Ποια κατηγορία τυπικών γλωσσών είναι αναγνωρίσιμη από ένα τύπο αυτομάτων; (Αναγνωρίσιμες γλώσσες)
- Είναι ορισμένα αυτόματα κλειστά υπό ένωση, τομή, ή συμπλήρωμα των τυπικών γλωσσών; (Ιδιότητες κλειστότητας)
- Πόσο εκφραστική είναι μια κατηγορία αυτομάτων όσον αφορά την αναγνώριση μιας κατηγορίας τυπικών γλωσσών; Ποια είναι η εκφραστική τους δύναμη; (Ιεραρχία γλωσσών)
Η θεωρία αυτομάτων επίσης μελετά αν υπάρχει αποτελεσματικός αλγόριθμος ή όχι που να λύνει προβλήματα παρόμοια με την παρακάτω λίστα.
- Δέχεται ένα αυτόματο οποιαδήποτε λέξη εισόδου; (Έλεγχος κενότητας)
- Μπορεί να μετατραπεί ένα δεδομένο μη ντετερμινιστικό αυτόματο σε ντετερμινιστικό αυτόματο χωρίς να αλλάξει η αναγνωρίσιμη γλώσσα; (Ντετερμινιστικοποίηση)
- Για μια δεδομένη τυπική γλώσσα, ποιο είναι το μικρότερο αυτόματο που την αναγνωρίζει;(Ελαχιστοποίηση αυτόματου).
Κατηγορίες Αυτομάτων
[Επεξεργασία | επεξεργασία κώδικα]Παρακάτω είναι μια ατελής λίστα με τους τύπους των αυτομάτων.
| Αυτόματα | Αναγνωρίσιμη γλώσσα |
|---|---|
| Ντετερμινιστικά πεπερασμένα αυτόματα(DFA) | Κανονικές γλώσσες |
| Μη ντετερμινιστικά πεπερασμένα αυτόματα(NFA) | Κανονικές γλώσσες |
| Μη ντετερμινιστικά πεπερασμένα αυτόματα με ε-μεταβάσεις (FND-ε or ε-NFA) | Κανονικές γλώσσες |
| Αυτόματα με στοίβα(PDA) | Γλώσσες χωρίς συμφραζόμενα |
| Γραμμικά περιορισμένα αυτόματα(LBA) | Γλώσσες με συμφραζόμενα |
| Μηχανές Τούρινγκ | Αναδρομικά απαριθμήσιμες γλώσσες |
| Χρονικά αυτόματα | |
| Ντετερμινιστικά Αυτόματα Büchi | Ωμέγα-περιορισμένες γλώσσες |
| Μη ντετερμινιστικά αυτόματα Büchi | Ωμέγα-κανονικές γλώσσες |
| Μη ντετερμινιστικά/ντετερμινιστικά αυτόματα Rabin | Ωμέγα-κανονικές γλώσσες |
| Αυτόματα Streett | Ωμέγα-κανονικές γλώσσες |
| Αυτόματα ισοτιμίας | Ωμέγα-κανονικές γλώσσες |
| Αυτόματα Muller | Ωμέγα-κανονικές γλώσσες |