Περιεχόμενα

Αλφάβητα και γλώσσες. Κανονικές εκφράσεις. Κανονικές γλώσσες. Μη-κανονικές γλώσσες. Γραμματικές χωρίς συμφραζόμενα. Γραμματικές χωρίς περιορισμούς.
Αυτόματα. Πεπερασμένα αυτόματα. Ντετερμινιστικά και μη-ντετερμινιστικά αυτόματα.
Αυτόματα στοίβας. Μηχανές Turing.
Θέση του Church. Turing αποφασίσιμες και αποδεκτές γλώσσες. Παγκόσμια μηχανή Turing. Μη υπολογισιμότητα. Μη επιλύσιμα προβλήματα.
Κλάσεις πολυπλοκότητας.