Αλφάβητα και γλώσσες. Πεπερασμένα αυτόματα. Ιδιότητες των πεπερασμένων αυτομάτων και των γλωσσών που δέχονται. Κανονικές εκφράσεις και κανονικές γλώσσες. Ισοδυναμία πεπερασμένων αυτομάτων και κανονικών εκφράσεων. Λήμμα άντλησης για κανονικές γλώσσες. Γραμματικές και η ιεραρχία του Chomsky. Γραμματικές και γλώσσες χωρίς συμφραζόμενα. Αυτόματα στοίβας και λήμμα άντλησης για γλώσσες χωρίς συμφραζόμενα. Ισοδυναμία γραμματικών χωρίς συμφραζόμενα και αυτομάτων στοίβας. Η έννοια της υπολογισιμότητας. Mηχανές Turing. Aποφασίσιμες και απαριθμήσιμες γλώσσες. Η θέση των Church-Turing. Eπιλύσιμα και μη επιλύσιμα προβλήματα. Το πρόβλημα του τερματισμού (halting problem). Εισαγωγή στην υπολογιστική πολυπλοκότητα. Χρονική πολυπλοκότητα, η κλάση Ρ, η θέση των Cook-Karp. Αναγωγή και πληρότητα. Μη-ντετερμινισμός και NP-πληρότητα, σχέση Ρ και ΝΡ, αλγοριθμικές συνέπειες NP-πληρότητας. Πολυπλοκότητα χώρου, η κλάση PSPACE, το θεώρημα του Savitch. PSPACE-πλήρη προβλήματα.
