Τυπικές γλώσσες και υπολογισιμότητα

(Διακριτά Μαθηματικά ΙI)
Μιχάλης Κολουντζάκης

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

E-mail: kolount AT member.ams.org

Φθινόπωρο 2003-04

1 Ωράριο

Τετάρτη 1-2, Πέμπτη 9-11 στην αίθουσα Α 101 (Ροτόντα).

Ώρες γραφείου: Τετάρτη 11-1.

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

Από τον οδηγό σπουδών του Τμήματος:

Ύλη

1. Υπολογισιμότητα και τυπικές γλώσσες
2. Μηχανές πεπερασμένων καταστάσεων
3. Ανάλυση αλγορίθμων
4. Αναδρομικές σχέσεις και αναδρομικοί αλγόριθμοι
5. Άλγεβρες Boole

Η έμφαση θα είναι στις τυπικές γλώσσες και μηχανές.

3 Βιβλίο

Θα χρησιμοποιηθούν οι διδακτικές σημειώσεις που έγραψα για το μάθημα το Φθινόπωρο 2002-03. Η παλιά μορφή των σημειώσεων βρίσκεται ακόμη στη σελίδα του μαθήματος αυτού.

• Κεφάλαια 1 και 2 σε μορφή Postscript (6 Οκτ. 2003)
• Κεφάλαια 3 και 4 σε μορφή Postscript (5 Νοε. 2003)
• Κεφάλαιο 5 σε μορφή Postscript (4 Νοε. 2003)
• Κεφάλαιο 6 σε μορφή Postscript (20 Ιαν. 2004)

4 Βαθμολογικό Σύστημα - Εξετάσεις

Θα υπάρξει μια προαιρετική πρόοδος που θα διαρκεί μια ώρα και θα μετράει 1/3 του τελικού βαθμού.

5 Ημερολόγιο μαθήματος

5.1 Εβδομάδα 6ης Οκτωβρίου 2003

Καλύψαμε το Κεφ. 1 των σημειώσεων αλλά όχι ολόκληρη την παράγραφο 1.3. Λύστε τις ασκήσεις του κεφαλαίου.

5.2 Εβδομάδα 13ης Οκτωβρίου 2003

Τελειώσαμε όλο το Κεφ. 1 των σημειώσεων και αρχίσαμε να μιλάμε για αυτόματα (μέχρι και την Άσκηση 23).

5.3 Εβδομάδα 20ης Οκτωβρίου 2003

Είδαμε πολλά παραδείγματα κατασκευής DFA και αρχίσαμε να μιλάμε για μη ντετερμινιστικά αυτόματα (NFA).

5.4 Εβδομάδα 27ης Οκτωβρίου 2003

Είδαμε πώς μετατρέπεται ένα NFA σε DFA. Επίσης τι είναι τα $\epsilon$-NFA. Και τα τρία μοντέλα είναι μεταξύ τους ισοδύναμα: αν μια γλώσσα αναγνωρίζεται από ένα είδος πεπερασμένου αυτομάτου (DFA, NFA ή $\epsilon$-NFA) τότε αναγνωρίζεται από όλα.

5.5 Εβδομάδα 3ης Νοεμβρίου 2003

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

5.6 Εβδομάδα 10ης Νοεμβρίου 2003

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

5.6.1 ΑΝΑΚΟΙΝΩΣΗ

Την εβδομάδα της 17ης Νοεμβρίου δε θα γίνει μάθημα λόγω απουσίας του διδάσκοντα.

5.7 Εβδομάδα 24ης Νοεμβρίου 2003

Είδαμε την απόδειξη του Λήμματος Άντλησης με κάθε λεπτομέρεια. Αρχίσαμε το Κεφ. 4, και είδαμε πώς μπορούμε, χρησιμοποιώντας συμπεράσματα του Λήμματος Άντλησης, να λύσουμε αλγοριθμιά διάφορα προβλήματα που αφορούν DFA, όπως, για παράδειγμα, το να ελέγχουμε αν δύο DFA αναγνωρίζουν την ίδια γλώσσα ή όχι. Επίσης αρχίσαμε να μιλάμε για την παράγραφο 4.2 και τις σχέσεις ισοδυναμίας $R_L$ και $R_M$ που ορίζονται για μια γλώσσα $L$ και ένα DFA $Μ$ αντίστοιχα.

5.7.1 ΑΝΑΚΟΙΝΩΣΗ (Πρόοδος)

Την Πέμπτη 18/12/2003 θα πραγματοποιηθεί διαγώνισμα προόδου από 9:30 έως 10:30 το πρωί, στις αίθουσες ΡΑ 101 (εκεί όπου κάνουμε μάθημα) και Θ 206. Η πρόοδος θα είανι προαιρετική και ο βαθμός θα μετράει το 1/3 του συνόλου. Η εξεταστέα ύλη θα είναι μέχρι και το Κεφ. 4.

5.8 Εβδομάδα 1ης Δεκεμβρίου 2003

Τελειώσαμε το Κεφ. 4, αφού είδαμε και τον αλγόριθμο (χωρίς πλήρη απόδειξη όμως) ελαχιστοποίησης των DFA, ο οποίος ήταν μια φυσική συνέπεια της απόδειξης του Θεωρήματος Myhill-Nerode.

5.9 Εβδομάδα 8ης Δεκεμβρίου 2003

Εισαγωγή στις context free γλώσσες και γραμματικές. Κάθε κανονική γλώσσα είναι και context free (με πλήρη απόδειξη και παραδείγματα του πώς μετατρέπουμε ένα DFA σε context free γραμματική).

5.10 Εβδομάδα 15ης Δεκεμβρίου 2003

Λεπτομερές παράδειγμα της §5.3 και διαγώνισμα προόδου στο μάθημα.

5.10.1 ΑΝΑΚΟΙΝΩΣΗ (Θέματα Προόδου)

Η πρόοδος πραγματοποιήθηκε στις 18/12/2003 από 9:30 έως 10:30.

Άσκηση 5.10.1   Κατασκευάστε DFA για τη γλώσσα εκείνων των λέξεων του ${\left\{{0,1}\right\}}^*$ που έχουν μέσα τουλάχιστον τρεις άσσους.

Άσκηση 5.10.2   Σε μια γλώσσα προγραμματισμού τα ονόματα μεταβλητών είναι οι λέξεις πάνω από το αλφάβητο $\Sigma={\left\{{a,b,0,1,2,\ldots,9}\right\}}$ που τα δυο πρώτα τους γράμματα είναι $a$ ή $b$ και των οποίων τα γράμματα από το τρίτο και μετά είναι $0,1,2,\ldots,9$. Π.χ. σωστά ονόματα μεταβλητών είναι τα $ab$, $ba0$, $aa090$, ενώ δεν είναι τα $aba$, $ab4b$ και $1ab$. Δώστε μια κανονική έκφραση που να περιγράφει τα ονόματα μεταβλητών.

Άσκηση 5.10.3   Δείξτε ότι η γλώσσα ${\left\{{a^kb^k:   k=0,1,2,\ldots}\right\}}$, πάνω από το αλφάβητο $\Sigma={\left\{{a,b}\right\}}$, δεν είναι κανονική.

5.10.2 ΑΝΑΚΟΙΝΩΣΗ (Αποτελέσματα Προόδου)

Βρίσκονται εδώ

5.10.3 ΑΝΑΚΟΙΝΩΣΗ (Αλλαγή αίθουσας)

Μέχρι νεωτέρας μεταφερόμαστε στην αίθουσα ΡΑ 203 (είσοδος από την είσοδο πρυτανείας).

5.11 Εβδομάδα 12ης Ιανουαρίου 2004

Είδαμε το υπολογιστικό μοντέλο του αυτομάτου με στοίβα (Push Down Automaton) το οποίο αναγνωρίζει ακριβώς τις γλώσσες που είναι context free. Είδαμε πώς να γράφουμε προγράμματα γι' αυτό το μοντέλο σε μια ψευδο-επέκταση της γλώσσας C. Επίσης είδαμε το Λήμμα Άντλησης για context free γλώσσες και το χρησιμοποιήσουμε για να αποδείξουμε ότι διάφορες γλώσσες δεν είναι context free.

5.12 Εβδομάδα 19ης Ιανουαρίου 2004

Μιλήσαμε για υπολογίσιμες (αναδρομικές) συναρτήσεις και σύνολα (γλώσσες), καθώς και για αναδρομικά απαριθμήσιμα σύνολα και γλώσσες.

5.12.1 ΑΝΑΚΟΙΝΩΣΗ (Τελικοί βαθμοί του μαθήματος για την περίοδο Φεβρουαρίου)

Βρίσκονται εδώ

5.12.2 ΑΝΑΚΟΙΝΩΣΗ (Τελικοί βαθμοί του μαθήματος για την περίοδο Σεπτεμβρίου)

Βρίσκονται εδώ