Θεωρία αυτομάτων: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Πίνακας με κατηγορίες |
section |
||
Γραμμή 11:
Τα αυτόματα παίζουν σημαντικό ρόλο στη [[θεωρία υπολογισμού]], τη σχεδίαση [[μεταγλωττιστής|μεταγλωττιστών]], και την [[τυπική επαλήθευση]].
==Θεωρία αυτομάτων==
Η θεωρία αυτομάτων είναι το πεδίο που μελετά τις ιδιότητες διαφόρων τύπων αυτομάτων. Για παράδειγμα, η ακόλουθες ερωτήσεις μελετώνται για κάθε τύπο αυτομάτων.
* Ποιά κατηγορία τυπικών γλωσσών είναι αναγνωρίσιμη από ένα τύπο αυτομάτων; (Αναγνωρίσιμες γλώσσες)
* Είναι ορισμένα αυτόματα ''κλειστά'' υπό ένωση, τομή, ή συμπλήρωμα των τυπικών γλωσσών; (Ιδιότητες κλειστότητας)
* Πόσο εκφραστική είναι μια κατηγορία αυτομάτων όσον αφορά την αναγνώριση μιας κατηγορίας τυπικών γλωσσών; Ποιά είναι η εκφραστική τους δύναμη; (Ιεραρχία γλωσσών)
Η θεωρία αυτομάτων επίσης μελετά αν υπάρχει [[αποτελεσματικός αλγόριθμος]] ή όχι που να λύνει προβλήματα παρόμοια με την παρακάτω λίστα.
* Δέχεται ένα αυτόματο οποιαδήποτε λέξη εισόδου; (Έλεγχος κενότητας)
* Μπορεί να μετατραπεί ένα δεδομένο μη ντετερμινιστικό αυτόματο σε ντετερμινιστικό αυτόματο χωρίς να αλλάξει η αναγνωρίσιμη γλώσσα; (Ντετερμινιστικοποίηση)
* Για μια δεδομένη τυπική γλώσσα, ποιό είναι το μικρότερο αυτόματο που την αναγνωρίζει;([[Ελαχιστοποίηση αυτόματου]]).
== Κατηγορίες Αυτομάτων ==
| |||