From Wikipedia, the free encyclopedia
Στη Θεωρητική πληροφορική, θεωρία αυτομάτων είναι η μελέτη των μαθηματικών αντικειμένων που ονομάζονται αφηρημένες μηχανές ή αυτόματα και των υπολογιστικών προβλημάτων που μπορούν να λυθούν με αυτά.
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Το σχήμα δεξιά παρουσιάζει μια μηχανή πεπερασμένων καταστάσεων, η οποία ανήκει σε μια γνωστή κατηγορία αυτομάτων. Το αυτόματο αυτό αποτελείται από καταστάσεις (που απεικονίζονται με κύκλους), και μεταβάσεις (που απεικονίζονται με βέλη). Καθώς το αυτόματο βλέπει ένα σύμβολο εισόδου, εκτελεί μια μετάβαση (ή πήδημα) σε άλλη κατάσταση, ανάλογα με τη συνάρτηση μετάβασης (η οποία δέχεται την τρέχουσα κατάσταση και το τελευταίο σύμβολο ως εισόδους).
Η θεωρία αυτομάτων είναι πολύ σχετική με τη θεωρία τυπικών γλωσσών. Ένα αυτόματο είναι η πεπερασμένη περιγραφή μιας τυπικής γλώσσας, η οποία μπορεί να είναι άπειρο σύνολο. Τα αυτόματα συνήθως κατηγοριοποιούνται ανάλογα με το είδος της τυπικής γλώσσας που αναγνωρίζουν.
Τα αυτόματα παίζουν σημαντικό ρόλο στη θεωρία υπολογισμού, τη σχεδίαση μεταγλωττιστών, και την τυπική επαλήθευση.
Η θεωρία αυτομάτων είναι το πεδίο που μελετά τις ιδιότητες διαφόρων τύπων αυτομάτων. Για παράδειγμα, η ακόλουθες ερωτήσεις μελετώνται για κάθε τύπο αυτομάτων.
Η θεωρία αυτομάτων επίσης μελετά αν υπάρχει αποτελεσματικός αλγόριθμος ή όχι που να λύνει προβλήματα παρόμοια με την παρακάτω λίστα.
Παρακάτω είναι μια ατελής λίστα με τους τύπους των αυτομάτων.
Αυτόματα | Αναγνωρίσιμη γλώσσα |
---|---|
Ντετερμινιστικά πεπερασμένα αυτόματα(DFA) | Κανονικές γλώσσες |
Μη ντετερμινιστικά πεπερασμένα αυτόματα(NFA) | Κανονικές γλώσσες |
Μη ντετερμινιστικά πεπερασμένα αυτόματα με ε-μεταβάσεις (FND-ε or ε-NFA) | Κανονικές γλώσσες |
Αυτόματα με στοίβα(PDA) | Γλώσσες χωρίς συμφραζόμενα |
Γραμμικά περιορισμένα αυτόματα(LBA) | Γλώσσες με συμφραζόμενα |
Μηχανές Τούρινγκ | Αναδρομικά απαριθμήσιμες γλώσσες |
Χρονικά αυτόματα | |
Ντετερμινιστικά Αυτόματα Büchi | Ωμέγα-περιορισμένες γλώσσες |
Μη ντετερμινιστικά αυτόματα Büchi | Ωμέγα-κανονικές γλώσσες |
Μη ντετερμινιστικά/ντετερμινιστικά αυτόματα Rabin | Ωμέγα-κανονικές γλώσσες |
Αυτόματα Streett | Ωμέγα-κανονικές γλώσσες |
Αυτόματα ισοτιμίας | Ωμέγα-κανονικές γλώσσες |
Αυτόματα Muller | Ωμέγα-κανονικές γλώσσες |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.