Διακριτά Μαθηματικά ΙI
(Τυπικές Γλώσσες)

Μιχάλης Κολουντζάκης

Τμήμα Μαθηματικών
Πανεπιστήμιο Κρήτης
Λεωφόρος Κνωσού
714 09 Ηράκλειο

E-mail: mk@fourier.math.uoc.gr

Φθινόπωρο 2002-03

Ημερομηνία τελευταίας ενημέρωσης: / /

Περιεχόμενα

• Περιεχόμενα
• 1 Ωράριο
• 2 Περιγραφή του μαθήματος
• 3 Βιβλίο
• 4 Βαθμολογικό Σύστημα - Εξετάσεις
• 5 Ημερολόγιο Μαθήματος (Διδακτικές σημειώσεις που γράφονται σιγά-σιγά)
  • 5.1 Τρ, 24/9/02: Εισαγωγικά
  • 5.2 Πα, 27/9/02: Μικρή επανάληψη. Δέντρα.
  • 5.3 Τρ, 1/10/02: Σχέσεις, ισοδυναμίες, μεταβατική κλειστότητα. Ντετερμινιστικά αυτόματα
    • 5.3.1 Σχέσεις ορισμένες σε σύνολα
    • 5.3.2 Μεταβατική κλειστότητα $R^+$ μιας σχέσης $R$
    • 5.3.3 Ντετερμινιστικά Αυτόματα - Εισαγωγή
  • 5.4 Πα, 4/10/02: Παραδείγματα από DFA. Μη ντετερμινιστικά αυτόματα (NFA).
    • 5.4.1 Παραδείγματα DFA
    • 5.4.2 Μη ντετερμινιστικά αυτόματα
  • 5.5 Τρ, 8/10/02: Ισοδυναμία NFA και DFA. NFA με $\epsilon$-κινήσεις
    • 5.5.1 Ισοδυναμία NFA και DFA.
    • 5.5.2 NFA με $\epsilon$-κινήσεις
  • 5.6 Πα, 11/10/02: Κανονικές εκφράσεις και γλώσσες. Σχέση με αυτόματα.
    • 5.6.1 Κανονικές εκφράσεις και οι γλώσσες τους
    • 5.6.2 Κανονικότητα γλωσσών των αυτομάτων
  • 5.7 Τρ, 22/10/02: Κλειστότητα κανονικών γλωσσών κάτω από απλές πράξεις. Το Λήμμα άντλησης.
    • 5.7.1 Κλειστότητα κανονικών γλωσσών
    • 5.7.2 Το Λήμμα Άντλησης (Pumping lemma) και μη κανονικές γλώσσες
  • 5.8 Τρ, 29/10/02, Πα 1/11/02: Αλγόριθμοι για DFA. Θεώρημα Myhill-Nerode
    • 5.8.1 Πότε ένα DFA αναγνωρίζει κενή ή άπειρη γλώσσα
    • 5.8.2 Σχέσεις ισοδυναμίας για γλώσσες και αυτόματα. Θεώρημα Myhill-Nerode
  • 5.9 Τρ, 5/11/02: Ελαχιστοποίηση DFA
  • 5.10 Δε, 18/11/02: Θέματα και αποτελέσματα Προόδου
  • 5.11 Context free γραμματικές και γλώσσες
    • 5.11.1 Ένας τρόπος περιγραφής απλών αριθμητικών εκφράσεων
    • 5.11.2 Ορισμός context free γραμματικών και των γλωσσών τους
    • 5.11.3 Ένα ενδιαφέρον παράδειγμα με πλήρη απόδειξη
    • 5.11.4 Οι κανονικές γλώσσες είναι και context free
    • 5.11.5 Το αυτόματο με στοίβα (Push Down Automaton)
    • 5.11.6 Παραδείγματα PDA
    • 5.11.7 Το Λήμμα Άντλησης για context free γλώσσες, και η εφαρμογή του
  • 5.12 Υπολογισιμότητα
    • 5.12.1 Υπολογίσιμες συναρτήσεις και αναδρομικά σύνολα
    • 5.12.2 Μη υπολογίσιμες συναρτήσεις
    • 5.12.3 Το Halting Problem. 'Αλλα μη αποφασίσιμα προβλήματα στα Μαθηματικά.
    • 5.12.4 Αναδρομικά απαριθμήσιμα (α.α.) σύνολα.
  • 5.13 Σά, 8/2/03: Θέματα και αποτελέσματα Τελικού Διαγωνίσματος
  • 5.14 Σεπτέμριος

Το κείμενο αυτό βρίσκεται εδώ σε μορφή Postscript.