Περιγραφή μαθήματος

Κωδικός μαθήματος: ΜΥΥ501

Εβδομαδιαίες ώρες διδασκαλίας: 3,2,0

Εξάμηνο σπουδών: 5ο

Διδακτικές Μονάδες: 4

Μονάδες ECTS: 6

Ιστοσελίδα Μαθήματος: http://www.cse.uoi.gr/~palios/automata/

Προσφερόμενο: Ακαδημαϊκό έτος 2023-2024

Προαπαιτούμενα:

Περιεχόμενο:

Κανονικές γλώσσες: κανονικές εκφράσεις, αιτιοκρατικά και μη αιτιοκρατικά πεπερασμένα αυτόματα, αναγνώριση γλώσσας από αυτόματο, ισοδυναμία αιτιοκρατικών και μη αιτιοκρατικών πεπερασμένων αυτομάτων, κατασκευή πεπερασμένου αυτόματου που αναγνωρίζει τη γλώσσα μιας κανονικής έκφρασης, κατάστρωση κανονικής έκφρασης για τη γλώσσα ενός πεπερασμένου αυτόματου, ιδιότητες κλειστότητας, λήμμα άντλησης για κανονικές γλώσσες και  χρήση του για την απόδειξη ότι κάποια γλώσσα δεν είναι κανονική, αλγόριθμοι για πεπερασμένα αυτόματα και κανονικές εκφράσεις.

Γλώσσες ανεξάρτητες συμφραζομένων: Γραμματικές ανεξάρτητες συμφραζομένων, αριστερότερη/δεξιότερη παραγωγή, συντακτικά δένδρα, ασαφείς γραμματικές, κανονικές γραμματικές ανεξάρτητες συμφραζομένων, αυτόματα στοίβας, μη ισοδυναμία αιτιοκρατικών και μη αιτιοκρατικών αυτομάτων στοίβας, ισοδυναμία του συνόλου των γλωσσών που αναγνωρίζονται από (μη αιτιοκρατικά) αυτόματα στοίβας και του συνόλου των γλωσσών που παράγονται από  γραμματικές ανεξάρτητες συμφραζομένων, κανονική μορφή Chomsky, ιδιότητες κλειστότητας, λήμμα άντλησης για γλώσσες ανεξάρτητες συμφραζομένων και  χρήση του για την απόδειξη ότι κάποια γλώσσα δεν είναι ανεξάρτητη συμφραζομένων, αλγόριθμοι για αυτόματα στοίβας και γραμματικές ανεξάρτητες συμφραζομένων.

Αναγνωρίσιμες και διαγνώσιμες (από μηχανή Turing) γλώσσες: Μηχανές Turing, αναγνώριση και διάγνωση γλώσσας από μηχανή Turing, ισοδυναμία αιτιοκρατικών και μη αιτιοκρατικών μηχανών Turing, απαρίθμηση γλώσσας, ισοδυναμία διαφορετικών μοντέλων μηχανών Turing, ιδιότητες κλειστότητας, εικασία των Church και Turing.

Μη επιλυσιμότητα: Επιλύσιμα προβλήματα για πεπερασμένα αυτόματα και κανονικές εκφράσεις, μια γλώσσα που δεν είναι διαγνώσιμη, το πρόβλημα του τερματισμού, αναγωγές, το πρόβλημα αντιστοιχίας του Post.

Κλάσεις P και NP.

Παρατηρήσεις: