Δ.Ε.Π. – Αρχική σελίδα

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

ΣΗΜΕΙΩΣΕΙΣ  ΜΑΘΗΜΑΤΟΣ  Υ5  ΤΟΥ  Δ.Ε.Π.

 

 

Προαπαιτούμενα και περιεχόμενα του μαθήματος

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

Το μάθημα αυτό προϋποθέτει ορισμένες γνώσεις θεμελιωδών εννοιών υπολογιστών (μάθημα Υ1), αλλά και μια κάποια μαθηματική παιδεία, καθώς βρίσκεται στην τομή των περιοχών των μαθηματικών και των υπολογιστών. Συγκεκριμένα, απαιτείται γνώση, προηγούμενη εκπαίδευση, και ιδίως ευχέρεια σε μαθηματικές αποδείξεις. Ειδικά η αποδεικτική μέθοδος της μαθηματικής επαγωγής ανασκοπείται στην εισαγωγική ενότητα (επειδή γίνεται χρήση-της σε πάμπολλα θεωρήματα), αλλά ο αναγνώστης δεν πρέπει να αναμένει να μάθει να αποδεικνύει μέσω επαγωγής στο παρόν μάθημα· πρέπει ήδη να κατέχει αυτή τη δεξιότητα που αποκτάται στο μάθημα Μ1. Βέβαια, η μαθηματική παιδεία δεν αποκτάται μόνο μέσω του μαθήματος Μ1, αλλά με τη γνώση και εκπαίδευση σε μια πλειάδα μαθημάτων μαθηματικού υποβάθρου· π.χ.: Λογική (Μ2), Θεωρία Συνόλων (Μ7), Θεωρία Αριθμών (Μ8), κ.ά.

Περιεχόμενα και στόχος

Το παρόν μάθημα αποτελεί τον “πυρήνα” της περιοχής γνώσης που λέγεται “επιστήμη υπολογιστών”· ήτοι, δεν νοείται να ισχυρίζεται κανείς οτι έχει σπουδάσει επιστήμη υπολογιστών χωρίς να έχει μελετήσει και αποκτήσει γνώση σε βάθος όλων των εννοιών που περιέχονται στο παρόν μάθημα. Ασχολείται με την έννοια της υπολογισιμότητας (αγγλ.: computability), και με τα διάφορα τυπικά συστήματα (αγγλ.: formal systems) μέσω των οποίων μπορούμε να ορίσουμε υπολογιστικές μηχανές. Δύο από αυτά τα τυπικά συστήματα είναι: 1. τα πεπερασμένα αυτόματα (αγγλ.: finite automata), και 2. οι τυπικές γλώσσες (αγγλ.: formal languages). Εξετάζει την ισοδυναμία μεταξύ κατηγοριών αυτομάτων και γλωσσών, και κατασκευάζει έτσι, βήμα-βήμα, το “απόσταγμα” της όλης θεωρίας της υπολογισιμότητας, που είναι η ιεραρχία του Τσόμσκι (αγγλ.: Chomsky hierarchy).

Στόχος του μαθήματος είναι η κατανόηση της έννοιας της υπολογισιμότητας· του πότε ένα πρόβλημα χαρακτηρίζεται αποφασίσιμο (αγγλ.: decidable) και πότε αναποφασίσιμο (αγγλ.: undecidable)· η κατανόηση των τεσσάρων κλάσεων τυπικών συστημάτων που αποτελούν την ιεραρχία του Τσόμσκι· και η κατανόηση σε βάθος του “αποστάγματος” της έννοιας “υπολογιστής”.

Θα μάθουμε για τα χαρακτηριστικά που πρέπει να έχει μια συσκευή έτσι ώστε να μπορούμε να πούμε οτι “υπολογίζει” κάτι. Θα γνωρίσουμε τέσσερις τέτοιες κατηγορίες συσκευών, η κάθε μια “υπολογιστικά πιο ισχυρή” (υπολογίζοντας πιο πολλές συναρτήσεις) από την προηγούμενη κατηγορία, και χωρίς κάποιον άλλο τύπο συσκευής να μπορεί να “χωρέσει ανάμεσα” σ’ αυτές τις τέσσερις. Η τέταρτη των κατηγοριών αυτών συσκευών, που είναι η Μηχανή Τούρινγκ (αγγλ.: Turing Machine), θα αποδειχθεί ο ισχυρότερος υπολογιστής που έχουμε φτιάξει ποτέ. Κάθε επιπλέον δυνατότητα που θα προσθέτουμε στη βασική Μηχανή Τούρινγκ θα αδυνατεί να προσθέσει ισχύ, με την έννοια οτι δεν θα υπάρχει καμιά συνάρτηση που να μπορεί να υπολογιστεί από την επαυξημένη συσκευή και που να μη μπορεί να υπολογιστεί κι από τη βασική Μηχανή Τούρινγκ. Έτσι θα συμπεράνουμε τη λεγόμενη Θέση των Τσερτς–Τούρινγκ, που λέει οτι η Μηχανή Τούρινγκ (ή όποια άλλη ισοδύναμη συσκευή) είναι ο ισχυρότερος υπολογιστής που μπορούμε ποτέ να φανταστούμε. Και, επειδή οι νευρώνες του εγκεφάλου μπορούν μάλλον εύκολα να εξισωθούν με μοντέλα υπολογιστικών συσκευών, η Θέση Τσερτς–Τούρινγκ έχει προεκτάσεις στην ανθρώπινη νόηση, προτείνοντας οτι οι σημερινοί υπολογιστές μπορεί να είναι ισοδύναμοι σε υπολογιστική ισχύ με τον ανθρώπινο εγκέφαλο. Αυτά και αρκετά άλλα ενδιαφέροντα θέματα περιλαμβάνονται στην ύλη του παρόντος μαθήματος.

Σαν βάση των σημειώσεων του παρόντος μαθήματος χρησιμοποιήθηκαν τα βιβλία που αναφέρονται στη βιβλιογραφία.


1. Εισαγωγικές έννοιες

Στην ενότητα αυτή θα κάνουμε μια σύντομη ανασκόπηση των θεμελιωδών εννοιών στις οποίες στηρίζεται και χρησιμοποιεί η θεωρία της υπολογισιμότητας.

1.1 Σύμβολα, αλφάβητα, συμβολοσειρές, και γλώσσες

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

Ορισμός: ένα αλφάβητο είναι ένα πεπερασμένο σύνολο συμβόλων.

Παραδείγματα αλφαβήτων είναι τα: {a, b, c}, {0, 1}, {z, $, 8, -}, κλπ. Συνήθως, για να μη μπερδευόμαστε, θα χρησιμοποιούμε λατινικά γράμματα ή ψηφία για τα σύμβολα ενός αλφαβήτου. Π.χ., από τα προηγούμενα παραδείγματα, τα {a, b, c} και {0, 1} είναι παραδείγματα αλφαβήτων που θα συναντάμε συχνά, καθώς άλλα σύμβολα (π.χ., τα +, *, κ.ά.) θα χρησιμοποιούνται για να δηλώνουν πράξεις μεταξύ αντικειμένων του μαθήματος. Θα χρησιμοποιούμε κεφαλαία ελληνικά γράμματα, όπως το Σ, για να συμβολίσουμε ολόκληρο το αλφάβητο· π.χ., Σ = {a, b}.

Ορισμός: μια συμβολοσειρά (αγγλ.: string) είναι μια ακολουθία συμβόλων που ανήκουν σε ένα αλφάβητο.

Παραδείγματα συμβολοσειρών είναι τα: babba, abba, aaaabbbb, κατασκευασμένα από το αλφάβητο {a, b}, αλλά και από το {a, b, c}, κλπ. Επίσης τα 1000, 1010101010, 000001, κατασκευασμένα από αλφάβητο που περιέχει τουλάχιστον τα σύμβολα 0 και 1· κ.ο.κ.

Δεχόμαστε την ύπαρξη της κενής συμβολοσειράς, που θα τη συμβολίζουμε με το ελληνικό πεζό γράμμα ε (σε πλάγια γραφή).

Θα χρησιμοποιούμε γράμματα σε πλάγια γραφή από το τέλος του λατινικού αλφαβήτου (w, x, y, z) για να δηλώνουμε συμβολοσειρές στη γενικότητά τους. Εξαίρεση θα αποτελεί, όπως είπαμε, η κενή συμβολοσειρά ε.

Ορισμός: το μήκος μιας συμβολοσειράς είναι ο αριθμός των συμβόλων που αποτελούν τη συμβολοσειρά. Θα χρησιμοποιούμε το συμβολισμό |w| για το μήκος της συμβολοσειράς w.

Π.χ., το |abba| είναι ίσο με 4, ενώ |ε| = 0.

Ορισμός: ένα πρόθεμα μιας συμβολοσειράς w είναι ένα αρχικό τμήμα της w· αντίστοιχα, μια κατάληξη της w είναι ένα τελικό τμήμα της w.

Π.χ., το aaa είναι πρόθεμα της aaaaab, ενώ το ab είναι κατάληξη της ίδιας συμβολοσειράς. Προφανώς το ε είναι τόσο πρόθεμα όσο και κατάληξη κάθε συμβολοσειράς. Επίσης προφανώς, κάθε συμβολοσειρά είναι πρόθεμα και κατάληξη του εαυτού-της.

Ορισμός: ένα γνήσιο πρόθεμα, και παρομοίως, μια γνήσια κατάληξη μιας συμβολοσειράς είναι οποιοδήποτε πρόθεμα ή κατάληξή της εκτός του εαυτού-της.

Ορισμός: το αποτέλεσμα της πράξης της συνένωσης (αγγλ.: concatenation) δύο συμβολοσειρών x και y είναι η συμβολοσειρά που προκύπτει από την απλή παράθεσή τους: xy.

Π.χ., η συνένωση των ab και ba είναι η abba. Η συνένωση των 0101 και ε είναι η 0101, που είναι επίσης η συνένωση των ε και 0101.

Η πράξη της συνένωσης έχει ασφαλώς την προσεταιριστική ιδιότητα, καθώς (xy)z = x(yz). Έτσι, θα γράφουμε απλά xyz εννοώντας τη συνένωση των x, y, και z, αφού η προτεραιότητα με την οποία εκτελούνται οι δύο συνενώσεις δεν παίζει ρόλο.

Ορισμός: μια τυπική γλώσσα (που θα την ονομάζουμε και απλώς γλώσσα) είναι ένα σύνολο συμβολοσειρών από το ίδιο αλφάβητο.

Παραδείγματα: το κενό σύνολο Ø, όπως και το σύνολο {ε}, είναι γλώσσες· η πρώτη με πληθάριθμο* 0, ενώ η δεύτερη με πληθάριθμο 1. Ας σημειωθεί οτι μια γλώσσα δεν απαιτείται να είναι πεπερασμένο σύνολο· μπορεί να είναι και άπειρο. Για το ακόλουθο παράδειγμα άπειρης γλώσσας θα χρειαστούμε έναν ορισμό:

Ορισμός: Μια συμβολοσειρά ονομάζεται παλίνδρομο αν (και μόνο αν)* διαβάζεται το ίδιο τόσο από αριστερά προς τα δεξιά όσο και από δεξιά προς τα αριστερά.

Το σύνολο όλων των παλινδρόμων από ένα αλφάβητο είναι μια άπειρη γλώσσα. Για παράδειγμα το σύνολο των παλινδρόμων του αλφαβήτου Σ = {a, b} είναι η γλώσσα: {ε, a, b, aa, bb, aaa, bbb, aba, bab, ...}. Θα χρησιμοποιούμε κεφαλαία λατινικά γράμματα για να συμβολίσουμε γλώσσες, π.χ.: L, G, κλπ.

Μια άλλη γλώσσα είναι το σύνολο όλων των συμβολοσειρών ενός αλφαβήτου Σ. Για τη γλώσσα αυτή θα χρησιμοποιούμε τον συμβολισμό Σ*. (Προσοχή: το Σ είναι αλφάβητο, ενώ το Σ* είναι γλώσσα.) Γενικά, το σύμβολο * θα το χρησιμοποιούμε για μια πράξη επί γλωσσών, που ονομάζεται “κλειστότητα Κλέινι” * (ή κλείσιμο Κλέινι, ή αστέρι Κλέινι· αγγλ.: Kleene closure):

Ορισμός: η κλειστότητα Κλέινι μιας γλώσσας L, που συμβολίζεται με το L*, είναι η γλώσσα που προκύπτει από τη συνένωση οποιουδήποτε αριθμού συμβολοσειρών της L.

Π.χ., αν L = {aa, ba}, τότε L* = {ε, aa, ba, aaaa, aaba, baaa, baba, ...}. Παρατηρούμε οτι η κλειστότητα Κλέινι είναι πάντοτε μια άπειρη γλώσσα.

Η κλειστότητα Κλέινι μπορεί να οριστεί παρόμοια και επί ενός αλφαβήτου Σ: πρόκειται για τη γλώσσα που προκύπτει από συνένωση οποιουδήποτε αριθμού συμβόλων του Σ.

Η πράξη αυτή ονομάζεται “κλειστότητα” (ή “κλείσιμο”) γιατί η επανάληψή της δεν δίνει νέο αποτέλεσμα: (L*)* = L*. Με άλλα λόγια, το σύνολο που προκύπτει έχει “κλείσει” (από άποψη νέων στοιχείων) με τη μία και μοναδική εφαρμογή της πράξης.

Άσκηση 1.1.1: Να αναγραφούν 8 στοιχεία της κλειστότητας L*, όπου L είναι η γλώσσα {ε, a, b, ba}. Μπορεί το ε να είναι ένα από αυτά τα στοιχεία; Μπορεί να είναι το εε;

1.2 Γράφοι και δέντρα

Για την εποπτική παράσταση* των πεπερασμένων αυτομάτων, τα οποία θα γνωρίσουμε στην επόμενη ενότητα, θα χρησιμοποιήσουμε τη δομή του γράφου.

Ορισμός: ένας γράφος G (αγγλ.: graph) είναι ένα διατεταγμένο ζεύγος πεπερασμένων συνόλων (V, E), όπου το V λέγεται το σύνολο των κορυφών (αγγλ.: vertices, ενικός vertex) του γράφου, ενώ το E, που λέγεται το σύνολο των ακμών (αγγλ.: edges) του γράφου, είναι ένα σύνολο (όχι απαραίτητα διατεταγμένων) ζευγών κορυφών από το V (ή αλλιώς: το Ε είναι μια διμελής σχέση του V).

Παράδειγμα:

Ο παραπάνω γράφος G = (V, E) έχει V = {1, 2, ..., 9} και Ε = {(i, j) | i + j = πρώτος αριθμός}.

Ορισμός: ένας κατευθυνόμενος γράφος (αγγλ.: directed graph) είναι ένας γράφος του οποίου το σύνολο των ακμών Ε είναι σύνολο διατεταγμένων ζευγών κορυφών από το V.

Συνεπώς, σε έναν κατευθυνόμενο γράφο έχει σημασία το “από” και το “προς” μιας ακμής (από ποια κορυφή ξεκινάει και προς ποια κορυφή καταλήγει). Ακολουθεί ένα παράδειγμα κατευθυνόμενου γράφου.

Ο παραπάνω γράφος G = (V, E) έχει V = {2, 3, ..., 9} και Ε = {(i, j) | i < j και i διαιρεί το j}.

Ορισμός: μια διαδρομή (αγγλ.: path) σε έναν γράφο G = (V, E) είναι μια ακολουθία κορυφών v1, v2, ..., vk από το V, με k > 0, έτσι ώστε να υπάρχει ακμή (vi, vi+1) i, 1 i < k. Το μήκος μιας τέτοιας διαδρομής είναι k – 1.

Όπως βλέπουμε από το προηγούμενο παράδειγμα, ένας γράφος δεν είναι απαραίτητο να είναι “ένα κομμάτι”. Όταν ο γράφος είναι “ένα κομμάτι”, ονομάζεται “συνεκτικός” (αγγλ.: connected). Όμως για όλες τις εποπτικές παραστάσεις πεπερασμένων αυτομάτων θα χρησιμοποιήσουμε κατευθυνόμενους γράφους, κανένας από τους οποίους δεν θα είναι “δύο κομμάτια” (ή περισσότερα). Γιαυτό δεν χρειάζεται να ορίσουμε τη συνεκτικότητα γράφων με τυπικό τρόπο.

Άσκηση 1.2.1: Να σχεδιαστεί ο γράφος G = (V, E) όπου V = {2, 3, ..., 9} και Ε = {(i, j) | i & j είναι πρώτοι προς αλλήλους}. (Δύο αριθμοί ονομάζονται “πρώτοι προς αλλήλους” όταν δεν έχουν κοινό διαιρέτη άλλον από τη μονάδα.) Είναι ο G κατευθυνόμενος ή μη; Υπάρχει διαδρομή από το 2 στο 8 στον G;

Ορισμός: σε μια ακμή (u, v) κατευθυνόμενου γράφου G, η κορυφή u λέγεται προκάτοχος της v, ενώ η v λέγεται διάδοχος της u.

Ορισμός: ένα δέντρο είναι ένας κατευθυνόμενος γράφος στον οποίο ισχύουν τα εξής:

  1. Υπάρχει μία κορυφή, που ονομάζεται ρίζα, που δεν έχει προκάτοχο, και από την οποία υπάρχει διαδρομή προς κάθε κορυφή.

  2. Κάθε κορυφή εκτός της ρίζας έχει ακριβώς έναν προκάτοχο.

  3. Οι διάδοχοι κάθε κορυφής είναι διατεταγμένοι.

Η διάταξη των διαδόχων μιας κορυφής σε ένα δέντρο (συνθήκη 3) μας επιτρέπει να τους σχεδιάζουμε από αριστερά προς τα δεξιά όταν δίνουμε τη γραφική απεικόνιση του δέντρου. Στις απεικονίσεις, τα δέντρα θα τα σχεδιάζουμε “ανάποδα”, με τη ρίζα επάνω και τους διαδόχους κάθε κορυφής από κάτω, διατεταγμένους.* Στο διάγραμμα που ακολουθεί δίνεται παράδειγμα ενός δέντρου, όπου κάθε κορυφή είναι το γινόμενο των διαδόχων-της.

Το παραπάνω δέντρο θα μπορούσε να οριστεί ως μια ανάλυση του αριθμού 990 σε γινόμενο πρώτων παραγόντων. Δέντρα θα χρησιμοποιήσουμε κυρίως για την παράσταση γραμματικών (“χωρίς συμφραζόμενα” και “με συμφραζόμενα”), σε επόμενες ενότητες. Προκειμένου για δέντρα, χρησιμοποιούμε μια κάπως πιο εξειδικευμένη ορολογία:

Ορισμός: σε ένα δέντρο, ο προκάτοχος λέγεται γονέας, ενώ οι διάδοχοι λέγονται τέκνα.

Π.χ., στο δέντρο του προηγούμενου παραδείγματος, ο γονέας της κορυφής που σημειώνεται με το “5” είναι η κορυφή “15”, ενώ τα τέκνα του “990” είναι τα “15” και “66”.

1.3 Αποδείξεις μέσω επαγωγής

Εδώ κάνουμε μια σύντομη ανασκόπηση της αποδεικτικής μεθόδου της μαθηματικής επαγωγής. Έστω οτι έχουμε μια πρόταση Π(ν), που εξαρτάται από ένα φυσικό αριθμό ν, και παίρνει τιμές “αλήθεια” ή “ψέμα” (πρόκειται δηλαδή για ένα κατηγόρημα). Η αρχή της μαθηματικής επαγωγής λέει οτι για να αποδείξουμε οτι η Π(ν) είναι αληθής, αρκεί να αποδείξουμε οτι:

  1. Π(0), και

  2. Π(ν – 1) → Π(ν) ν 1.

Τη συνθήκη (1), παραπάνω, τη λέμε επαγωγική βάση, ενώ τη συνθήκη (2) τη λέμε επαγωγικό βήμα. Τη σχέση Π(ν – 1) στην (2) τη λέμε επαγωγική υπόθεση, ενώ τη σχέση Π(ν) στη (2) τη λέμε επαγωγικό συμπέρασμα (αγγλ.: inductive basis, step, hypothesis, & conclusion).

Παράδειγμα: έστω οτι η πρόταση Π(ν) που θέλουμε να αποδείξουμε είναι η εξής ισότητα:

Αποδεικνύουμε την Π(ν) με επαγωγή. Η επαγωγική βάση, Π(0), ισχύει κατά τετριμμένο τρόπο: 0 = 0(0+1)/2, ήτοι 0 = 0. Για το επαγωγικό βήμα τώρα, έχουμε από την υπόθεση Π(ν – 1) πως ν 1 ισχύει οτι:

και θέλουμε να συνάγουμε την Π(ν), επίσης ν 1. Προσθέτοντας το ν και στα δύο μέλη της Π(ν – 1), παίρνουμε:

Παρατηρούμε οτι το αριστερό και το δεξί μέλος της παραπάνω πολλαπλής ισότητας είναι ακριβώς η Π(ν). Άρα η Π(ν) ισχύει.

(Στην παραπάνω απόδειξη βλέπουμε και τη χρήση του συμβόλου ▓ που θα κάνουμε για να συμβολίζουμε το «όπερ έδει δείξαι» στο τέλος κάθε απόδειξης.)

Άσκηση 1.3.1: Να αποδειχτεί με χρήση επαγωγής ως προς ν η ισότητα:

Άσκηση 1.3.2: Να αποδειχτεί με χρήση επαγωγής ως προς ν η ισότητα:

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

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

νιψονανομηματαμημονανοψιν

madaminedenimadam

Θέλουμε τώρα να αποδείξουμε το παρακάτω:

Θεώρημα: αν μια συμβολοσειρά x είναι παλίνδρομο, τότε είναι μέλος του μικρότερου συνόλου P το οποίο:

  1. περιλαμβάνει το ε,

  2. περιλαμβάνει κάθε σύμβολο a του αλφαβήτου,

  3. περιλαμβάνει όλες τις συμβολοσειρές της μορφής aya όπου το a είναι οποιοδήποτε σύμβολο και  y P.

Απόδειξη (με επαγωγή στο μήκος του x):

Ας υποθέσουμε οτι η συμβολοσειρά x είναι παλίνδρομο, δηλαδή διαβάζεται το ίδιο και προς τις δύο διευθύνσεις. Θα αποδείξουμε το θεώρημα μέσω επαγωγής επί του μήκους του x. Αν |x| 1, τότε το x είναι είτε το ε, οπότε ισχύει η συνθήκη 1, είτε ένα απλό σύμβολο a, οπότε ισχύει η συνθήκη 2. Αν τώρα το |x| > 1, τότε εφόσον το x διαβάζεται το ίδιο και προς τις δύο διευθύνσεις, αρχίζει και τελειώνει με το ίδιο σύμβολο a, άρα γράφεται σαν aya, όπου το y έχει μήκος μικρότερο του |x|. Από την επαγωγική υπόθεση, μία από τις συνθήκες 1, 2, ή 3 ισχύει για το y, και y P. Επομένως το x = aya ικανοποιεί τη συνθήκη 3.


2. Πεπερασμένα Αυτόματα

2.1 Αιτιοκρατικά Πεπερασμένα Αυτόματα

Ένα πεπερασμένο αυτόματο (ΠΑ, αγγλ.: finite automaton) είναι ένα μαθηματικό μοντέλο ενός συστήματος (μπορεί να είναι ένα φυσικό σύστημα — θα δούμε παραδείγματα αμέσως) που ανά πάσα στιγμή μπορεί να βρίσκεται σε μια κατάσταση ή καταστάσεις (αγγλ.: states), έχοντας επεξεργαστεί κάποια δεδομένα εισόδου (αγγλ.: input data). Προαιρετικά, το ΠΑ μπορεί να έχει αποδεχτεί (αγγλ.: accepted) τα δεδομένα εισόδου ευρισκόμενο σε μια τελική κατάσταση (αγγλ.: final state)· αλλιώς, αν τα δεδομένα εισόδου τελείωσαν και το ΠΑ δεν βρίσκεται σε τελική κατάσταση, τότε απορρίπτει (αγγλ.: rejects) τα δεδομένα εισόδου. Προαιρετικά επίσης, μπορεί κατά τη λειτουργία-του να έχει δημιουργήσει ορισμένα δεδομένα εξόδου (αγγλ.: output data).

Απλό παράδειγμα ενός ΠΑ είναι ένας ανελκυστήρας παλαιού τύπου (ηλεκτρικός, όχι ηλεκτρονικός). Η κατάσταση στην οποία βρίσκεται ο ηλεκτρικός ανελκυστήρας είναι ο όροφος στον οποίο σταθμεύει ανά πάσα στιγμή, ενώ χάριν απλότητας αγνοούμε το χρόνο που μεσολαβεί καθώς ο ανελκυστήρας κινείται από όροφο σε όροφο. Τα δεδομένα εισόδου που έχει επεξεργαστεί ο ανελκυστήρας είναι τα κουμπιά κλήσης που πατήθηκαν είτε από χρήστες που εξυπηρετήθηκαν από διάφορους ορόφους, είτε μέσα από τον ανελκυστήρα. Ο ηλεκτρικός ανελκυστήρας δεν έχει μνήμη, συνεπώς το κάθε κουμπί κλήσης που πατιέται σε έναν όροφο μπαίνει σαν “επόμενο δεδομένο εισόδου” αν ο ανελκυστήρας δεν κινείται. (Αν κινείται, τα πατήματα κουμπιών αγνοούνται σε τέτοιους ανελκυστήρες.) Γίνεται άμεση επεξεργασία αυτού του δεδομένου εισόδου, δηλαδή ο ανελκυστήρας αλλάζει κατάσταση, μεταφερόμενος στον όροφο που έγινε η κλήση. Επίσης, ο ανελκυστήρας (γενικά) είναι κάπως ειδικού τύπου αυτόματο, γιατί δεν έχει τελική κατάσταση (δεν σταματά να λειτουργεί ποτέ· δεν έρχεται ποτέ σε κατάσταση “τέλος, δεν εξυπηρετώ άλλα δεδομένα”).

Ο ακόλουθος γράφος δείχνει σχηματικά ένα ΠΑ που αποτελεί μοντέλο ανελκυστήρα για τρεις ορόφους:


ΠΑ ανελκυστήρα τριών ορόφων

Στον παραπάνω γράφο, το ΠΑ που απεικονίζεται “μοντελοποιεί” έναν ανελκυστήρα τριών ορόφων, όπου η κατάσταση q0 σημαίνει οτι ο ανελκυστήρας είναι σταθμευμένος στο ισόγειο, η q1 στον πρώτο όροφο, και η q2 στο δεύτερο όροφο. Τα βέλη που φεύγουν από κάθε κατάσταση δείχνουν σε ποια κατάσταση θα βρεθεί το αυτόματο με το πάτημα του κουμπιού του αντίστοιχου ορόφου. Π.χ., όταν ο ανελκυστήρας είναι στο ισόγειο (q0), το πάτημα του κουμπιού του ισογείου (0) δεν έχει κανένα αποτέλεσμα, και ο ανελκυστήρας παραμένει στην κατάσταση q0. Αντίθετα, από την q0, με το πάτημα του κουμπιού για τον πρώτο όροφο, το ΠΑ μεταφέρεται στην κατάσταση q1 (“στάθμευση στον πρώτο όροφο”), ενώ με το πάτημα του κουμπιού για το δεύτερο όροφο μεταφέρεται αντίστοιχα στην κατάσταση q2 (“στάθμευση στο δεύτερο όροφο”). Τα κουμπιά 0, 1, και 2 είναι τα δεδομένα εισόδου. Η κάθε κατάσταση qi πρέπει να ανταποκρίνεται σε κάθε δεδομένο εισόδου i, οπου i = 0, 1, 2, προκειμένου ο ανελκυστήρας να λειτουργεί σωστά. Επίσης βλέπουμε μια σύμβαση που θα κάνουμε στα διαγράμματα όλων των αυτομάτων: η αρχική κατάσταση (q0) θα διακρίνεται από τις άλλες με το βέλος που καταλήγει σ’ αυτήν “από το πουθενά” (οριζόντιο στο σχήμα).

Ο ηλεκτρονικός ανελκυστήρας διαφέρει κατά ουσιαστικό τρόπο από τον ηλεκτρικό, γιατί περνάει από κατάσταση σε κατάσταση κατά διαφορετικό τρόπο από τον ηλεκτρικό, καθώς οι κλήσεις από το εσωτερικό του θαλάμου παίρνουν προτεραιότητα σε σχέση με όσες γίνονται από τους ορόφους. Επίσης, μπορεί να “επιλέξει” να εξυπηρετήσει πρώτα τον όροφο που βρίσκεται κοντύτερα στον παρόντα, παρά τον πιο μακρυνό. Έτσι, ο ηλεκτρονικός ανελκυστήρας λειτουργεί βάσει “προγράμματος”, το οποίο ξεπερνά σε υπολογιστική ισχύ ένα ΠΑ (χρειάζεται αυτόματο μεγαλύτερων υπολογιστικών δυνατοτήτων, από αυτά τα οποία θα συναντήσουμε σε επόμενες ενότητες). Γιαυτό εδώ θα παραμείνουμε στο παράδειγμα του ηλεκτρικού ανελκυστήρα.

Ας κάνουμε μια τροποποίηση στην ιδέα “ανελκυστήρας”. Ενώ κανονικά η δουλειά του ανελκυστήρα είναι να εξυπηρετεί (ατέρμονα, δίχως σταματημό) τους χρήστες, ας υποθέσουμε οτι έχουμε έναν ανελκυστήρα με ειδικό “σκοπό”: ο σκοπός-του είναι να φτάσει στο 2ο όροφο· όταν φτάσει εκεί, παύει να λειτουργεί. Έτσι, μπορούμε να πούμε οτι ο ανελκυστήρας αυτός έχει μια τελική κατάσταση, την q2, την οποία θα συμβολίζουμε με διπλό κύκλο, όπως στο ακόλουθο διάγραμμα:


ΠΑ ανελκυστήρα με τελική κατάσταση q2

Επιπλέον παρατηρούμε οτι, χάρη στην τελική κατάσταση, το αυτόματο αυτό, ξεκινώντας από την αρχική κατάσταση q0, αποδέχεται την ακολουθία δεδομένων (δηλ. πατημάτων κουμπιών) 1010012, γιατί αφού ανταποκριθεί στα δεδομένα αυτά καταλήγει στην κατάσταση q2, που είναι τελική. Επομένως αποδέχεται τη συμβολοσειρά 1010012. Αντίθετα, απορρίπτει τη συμβολοσειρά 01011, γιατί αυτή δεν το οδηγεί στην τελική q2. Ας σημειωθεί οτι αποδέχεται επίσης τη συμβολοσειρά 00222, γιατί δεν είναι απαραίτητο να σταματήσει με το που θα βρεθεί σε τελική κατάσταση· σημασία για την αποδοχή ή απόρριψη έχει το σε ποια κατάσταση βρίσκεται το αυτόματο με την επεξεργασία και του τελευταίου δεδομένου εισόδου.

Επομένως ένα αυτόματο μπορούμε να το δούμε σαν μηχανή που αποδέχεται ή απορρίπτει μια συμβολοσειρά δεδομένων εισόδου.

Άσκηση 2.1.1: Να κατασκευαστεί ο γράφος ενός ΠΑ το οποίο αποδέχεται όλες τις συμβολοσειρές (και μόνο αυτές) που αποτελούνται από 0 και 1 και που έχουν τουλάχιστον τρία διαδοχικά 1.

Άσκηση 2.1.2: Να κατασκευαστεί ο γράφος ενός ΠΑ το οποίο αποδέχεται όλες τις συμβολοσειρές (και μόνο αυτές) που αποτελούνται από 0 και 1 και που έχουν άρτιο αριθμό από 0.

Άσκηση 2.1.3: Θεωρήστε τη λειτουργία ενός θερμοστάτη (π.χ. για αερόθερμο μπάνιου). Ο θερμοστάτης βάζει το μηχάνημα σε λειτουργία όταν η θερμοκρασία πέσει κάτω από ένα όριο, π.χ. τους 20°C, ενώ όταν η θερμοκρασία ξεπεράσει ένα άλλο όριο, π.χ. τους 25°C, τότε ο θερμοστάτης διακόπτει το ηλεκτρικό ρεύμα και σταματάει το μηχάνημα. Φτιάξτε ένα μοντέλο της λειτουργίας του θερμοστάτη ως ΠΑ με ένα γράφο. Κάντε την απλοποιητική υπόθεση οτι η θερμοκρασία μπορεί να είναι μόνο τριών ειδών: a = “κάτω των 20°C”, b = “μεταξύ 20°C και 25°C (περιλαμβανομένων των δύο ορίων)”, και c = “άνω των 25°C”. Αποφασίστε ποιες είναι οι καταστάσεις του θερμοστάτη (ας μην υπάρχει τελική κατάσταση), και πότε μεταφέρεται από τη μια κατάσταση στην άλλη.

Ορισμός: ένα πεπερασμένο αυτόματο είναι μια πενταπλή πλειάδα (Q, Σ, δ, q0, F), όπου το Q είναι ένα πεπερασμένο σύνολο καταστάσεων, το Σ ένα πεπερασμένο αλφάβητο εισόδου, η δ μια συνάρτηση μετάβασης που απεικονίζει το Q X Σ → Q, το q0 Q η αρχική κατάσταση, και το F ένα σύνολο τελικών καταστάσεων.

Η συνάρτηση μετάβασης δ (αγγλ.: transition function) προσδιορίζει σε ποια κατάσταση q' θα βρεθεί το αυτόματο για κάθε κατάσταση q και κάθε σύμβολο εισόδου a; ήτοι, δ(q, a) = q'.

Για παράδειγμα, το ΠΑ του ανελκυστήρα που συζητήθηκε νωρίτερα, έχει Q = {q0, q1, q2}, Σ = {0, 1, 2}, αρχική κατάσταση q0, F = {q2}, και μια δ που ορίζεται ως ακολούθως:

δ 0 1 2
q0 q0 q1 q2
q1 q0 q1 q2
q2 q0 q1 q2

Τα αιτιοκρατικά πεπερασμένα αυτόματα (θα τα συντομογραφούμε ως ΑΠΑ), είναι αυτόματα όπως τα ανωτέρω, στα οποία κάθε κατάσταση και σύμβολο εισόδου αντιστοιχίζεται σε μία και μοναδική κατάσταση. (Στην επόμενη υποενότητα θα συναντήσουμε τα μη-αιτιοκρατικά ΠΑ.) Αιτιοκρατία (αγγλ.: determinism) σημαίνει οτι, έχοντας μια τρέχουσα κατάσταση και ένα σύμβολο, γνωρίζουμε σε ποια επόμενη κατάσταση θα βρεθεί το αυτόματο. (Μη-αιτιοκρατία, αγγλ.: nondeterminism, σημαίνει οτι δεν γνωρίζουμε συγκεκριμένα σε ποια κατάσταση θα βρεθεί, γιατί μπορεί να βρίσκεται σε ολόκληρο σύνολο καταστάσεων.)

Η συνάρτηση μετάβασης δ μπορεί εύκολα να επεκταθεί σε μια συνάρτηση δ΄ ώστε η δ΄ να εφαρμόζει επί συμβολοσειρών αντί επί μεμονομένων συμβόλων, ως εξής:

  1. δ΄(q, ε) = q

  2. δ΄(q, wa) = δ (δ΄(q, w), a), για όλες τις συμβολοσειρές w και όλα τα σύμβολα εισόδου a.

Αν εφαρμόσουμε τη δ΄ σε ένα μεμονωμένο σύμβολο εισόδου a, παρατηρούμε οτι δ΄(q, a) = δ(q, a) (η αιτιολόγηση αυτού αφήνεται σαν άσκηση). Έτσι, καθώς δεν μπορεί να γίνει σύγχυση για το ποια από τις δύο συναρτήσεις, δ΄ ή δ, εννοείται (διακρίνονται λόγω του είδους της δεύτερης παραμέτρου-τους, που είναι συμβολοσειρά ή σύμβολο, αντιστοίχως), και καθώς τα αποτελέσματά τους σε μεμονωμένα σύμβολα είναι ταυτόσημα, θα πάψουμε να γράφουμε τη δ΄ και θα χρησιμοποιούμε τη δ, ακόμα και με συμβολοσειρές.

Ορισμός: μια συμβολοσειρά x γίνεται αποδεκτή από ένα πεπερασμένο αυτόματο M = (Q, Σ, δ, q0, F) αν p F: δ(q0, x) = p.
Αν η συμβολοσειρά δεν γίνεται αποδεκτή από το Μ, τότε λέμε οτι απορρίπτεται από αυτό.

Άσκηση 2.1.4: Δίνεται το αυτόματο που εικονίζεται* στο παρακάτω διάγραμμα:

Αποφασίστε αν το παραπάνω αυτόματο αποδέχεται τις συμβολοσειρές: 01, 001, 111010101, 000010101, και 1110101010.

Άσκηση 2.1.5: Ο ορισμός ενός ΑΠΑ (του μόνου τύπου ΠΑ που έχουμε δει μέχρι τώρα) απαιτεί οτι η συνάρτηση μετάβασης δ είναι ολική, δηλ. ορίζεται για κάθε σύμβολο εισόδου σε κάθε κατάσταση. Θεωρήστε την περίπτωση μιας μερικής δ, η οποία ορίζεται μεν για κάθε κατάσταση, αλλά όχι απαραίτητα για κάθε σύμβολο εισόδου σε κάθε κατάσταση. Για παράδειγμα, η δ που εμφανίζεται σε έναν πίνακα παραπάνω (στο “ΠΑ του ανελκυστήρα”) θα μπορούσε να δίνεται ως εξής:

δ 0 1 2
q0 q0   q2
q1 q0 q1  
q2   q1 q2

(Αυτό θα αντιστοιχούσε σε έναν ανελκυστήρα με μερικά “χαλασμένα” κουμπιά.) Ας υποθέσουμε οτι τροποποιούμε τον ορισμό του ΑΠΑ ώστε να μπορεί να συμπεριλάβει και τις μερικές συναρτήσεις μετάβασης, ως εξής: αν το αυτόματο βρεθεί σε κατάσταση στην οποία το σύμβολο εισόδου δεν ορίζεται (π.χ., η κατάσταση q0 με το 1 σαν επόμενο σύμβολο εισόδου στο παραπάνω παράδειγμα) τότε το αυτόματο απορρίπτει τη συμβολοσειρά εισόδου. Δείξτε οτι μπορούμε πάντα να κατασκευάσουμε ένα ισοδύναμο* ΑΠΑ με μια ολική συνάρτηση δ το οποίο αποδέχεται και απορρίπτει ακριβώς τις ίδιες συμβολοσειρές με εκείνες που αποδέχεται και απορρίπτει το ΑΠΑ με τη μερική συνάρτηση δ.

Ορισμός: η γλώσσα που αναγνωρίζεται από το πεπερασμένο αυτόματο Μ είναι το σύνολο των συμβολοσειρών: {x | δ(q0, x) F}.

Ας σημειωθεί οτι ένα αυτόματο μπορεί να κάνει αποδεκτές πολλές συμβολοσειρές, αλλά αναγνωρίζει μόνο μία γλώσσα.

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

Θα χρησιμοποιούμε το συμβολισμό L(M) για να δηλώνουμε τη γλώσσα L που αναγνωρίζεται από το αυτόματο M.

Άσκηση 2.1.6: Απαριθμήστε λίγα ακόμα από τα στοιχεία της γλώσσας που αναγνωρίζεται από το ΠΑ της άσκησης 2.1.4. Τώρα προσπαθήστε να δώσετε μια περιγραφή στα ελληνικά όλων των συμβολοσειρών της γλώσσας εκείνης.

Ορισμός: μια γλώσσα λέγεται κανονικό σύνολο (αγγλ.: regular set) αν είναι η γλώσσα που αναγνωρίζεται από κάποιο πεπερασμένο αυτόματο. Μια τέτοια γλώσσα ονομάζεται επίσης κανονική γλώσσα (αγγλ.: regular language).

Άσκηση 2.1.7: Θεωρήστε τη γλώσσα που αποτελείται από συμβολοσειρές οι οποίες είναι οι δυαδικές αναπαραστάσεις ακεραίων n τέτοιων ώστε n 1 mod 4 (δηλαδή αφήνουν υπόλοιπο 1 διαιρούμενοι διά 4). Είναι αυτή μια κανονική γλώσσα; Αν όχι, εξηγήστε γιατί. Αν ναι, κατασκευάστε ένα ΠΑ που να την αναγνωρίζει.

2.2 Μη-αιτιοκρατικά Πεπερασμένα Αυτόματα

Νωρίτερα μιλήσαμε για την αιτιοκρατία στα ΠΑ, που σημαίνει οτι έχοντας μια κατάσταση q και ένα σύμβολο εισόδου a, υπάρχει μόνο ένα βέλος που φεύγει από την q και είναι σημειωμένο με το a. (Με άλλα λόγια, η συνάρτηση μετάβασης δ είναι μια αληθινή συνάρτηση.) Χρησιμοποιήσαμε το ακρόστιχο “ΑΠΑ” για τα αιτιοκρατικά ΠΑ. Τώρα θα συναντήσουμε τα μη-αιτιοκρατικά ΠΑ (“ΜΠΑ”) στα οποία, όταν δίνεται μια κατάσταση q και ένα σύμβολο εισόδου a, μπορεί να υπάρχουν περισσότερα από ένα βέλη που να φεύγουν από την q και να έχουν ετικέτα a. Σε μια τέτοια περίπτωση, το ΜΠΑ περνά όχι σε μια και μοναδική κατάσταση, αλλά σε όλες τις καταστάσεις που είναι προσβάσιμες από την q με βέλη που έχουν ετικέτα a. Με άλλα λόγια, η δ δεν είναι πλέον συνάρτηση μετάβασης, αλλά μια απεικόνιση πολλαπλών τιμών (αγγλ.: mapping), που απεικονίζει την q σε ένα σύνολο διαδόχων καταστάσεων.

Ένας άλλος τρόπος για να δούμε τη λειτουργία ενός ΜΠΑ είναι οτι κάθε φορά που το αυτόματο συναντά n επιλογές για κάθε σύμβολο εισόδου σε μια κατάσταση, “διαχωρίζεται” σε n αντίγραφα του εαυτού-του, και κάθε αντίγραφο συνεχίζει να δουλεύει με τα στοιχεία εισόδου ανεξάρτητα από τα άλλα αντίγραφα. Φυσικά, ο διαχωρισμός αυτός μπορεί να συμβεί πάλι: αν ένα από τα αντίγραφα συναντήσει m επιλογές, διαχωρίζεται εκ νέου σε m επιλογές, καθεμία από τις οποίες προχωρά ανεξάρτητα από όποια άλλα αντίγραφα έχουν δημιουργηθεί μέχρι τότε. Οι φυσικοί πρέπει να είναι εξοικειωμένοι με αυτόν τον τρόπο λειτουργίας των ΜΠΑ, που θυμίζει την κβαντομηχανική “ερμηνεία πολλαπλών κόσμων”, του Hugh Everett.

Πότε μπορεί να αποδεχτεί ένα ΜΠΑ την είσοδο; Μπορεί όταν οποιοδήποτε από τα αντίγραφά του (που λειτουργούν ανεξάρτητα) φτάσει σε τελική κατάσταση.*

Το παρακάτω είναι παράδειγμα ενός ΜΠΑ:

Το παραπάνω ΜΠΑ αποδέχεται όλες τις συμβολοσειρές με 0 ή 1 που τελειώνουν είτε σε 00, είτε σε 11. Είναι μη-αιτιοκρατικό γιατί στην κατάσταση q0 με το στοιχείο εισόδου 0 έχει δύο επιλογές: είτε να μείνει στην κατάσταση q0, είτε να αλλάξει στην q1. Το ίδιο ισχύει και με το σύμβολο εισόδου 1, αλλά η ύπαρξη μιας και μόνο πολλαπλής επιλογής αρκεί για να χαρακτηρίσει ένα ΠΑ σαν ΜΠΑ.

Άσκηση 2.2.1: Χρησιμοποιώντας το προηγούμενο παράδειγμα σαν οδηγό, κατασκευάστε τον γράφο ενός ΜΠΑ που αποδέχεται όλες τις ελληνικές λέξεις που τελειώνουν σε “-ει” και μόνο αυτές. (Μπορείτε να χρησιμοποιήσετε συντομογραφία για να αποφύγετε να ζωγραφίσετε από ένα βέλος για κάθε γράμμα του αλφαβήτου.) Τώρα σκεφτείτε πώς θα έπρεπε να κατασκευαστεί ο γράφος σαν ΑΠΑ. Τί παρατηρείτε;

Ορισμός: ένα μη-αιτιοκρατικό πεπερασμένο αυτόματο είναι μια πενταπλή πλειάδα M = (Q, Σ, δ, q0, F), όπου τα Q, Σ, q0, και F έχουν το ίδιο νόημα όπως και στον ορισμό του ΑΠΑ, αλλά το δ είναι μια απεικόνιση: Q X Σ P (Q), όπου το P (Q) είναι το δυναμοσύνολο του Q (το σύνολο όλων των υποσυνόλων του Q).

Όπως και με τα ΑΠΑ, η απεικόνιση μετάβασης δ μπορεί να επεκταθεί ώστε να δέχεται συμβολοσειρές αντί για μεμονωμένα στοιχεία εισόδου, κατά παρόμοιο τρόπο (οι τυπικές λεπτομέρειες αφήνονται σαν άσκηση). Έτσι, μπορούμε να γράψουμε: δ: Q X Σ* P (Q). Επιπρόσθετα όμως, εδώ είναι χρήσιμο να επεκτείνουμε τη δ και έτσι ώστε να δέχεται σύνολα καταστάσεων, αντί για μεμονωμένες καταστάσεις: δ: P (Q) X Σ* P (Q). Αυτή η τελευταία επέκταση γίνεται ως εξής:

PQ. Έτσι μπορούμε να μιλάμε και πάλι για την L(M), τη γλώσσα που αναγνωρίζεται από το ΜΠΑ M, που είναι η:

L(M) = {w | δ(q0, w) περιέχει μια κατάσταση q F}.

2.3 Ισοδυναμία μεταξύ ΑΠΑ και ΜΠΑ

Διαισθητικά, ένα ΜΠΑ μοιάζει να είναι “ικανότερο” από ένα ΑΠΑ· ήτοι, να μπορεί να αναγνωρίσει περισσότερες γλώσσες, γιατί μπορεί να προσομοιώσει ένα ΑΠΑ (με την έννοια οτι κάθε ΑΠΑ είναι ένα ΜΠΑ το οποίο στην απεικόνιση μετάβασής του, δ, τυχαίνει να μην έχει περισσότερες από μια καταστάσεις–διαδόχους δοσμένης μιας κατάστασης και ενός συμβόλου εισόδου). Όμως, όπως θα δούμε αμέσως, αυτή η διαίσθηση αποδεικνύεται λανθασμένη: τα ΜΠΑ αναγνωρίζουν ακριβώς τις ίδιες γλώσσες όπως και τα ΑΠΑ, δηλαδή τις κανονικές γλώσσες. Αυτό δηλώνεται στο ακόλουθο θεώρημα:

Θεώρημα 2.3.1: μια γλώσσα L αναγνωρίζεται από ένα ΜΠΑ αν και μόνο αν αναγνωρίζεται από ένα ΑΠΑ.

Απόδειξη. Η κατεύθυνση “αν” του θεωρήματος είναι προφανής: αν η γλώσσα L είναι κανονική, δηλαδή αναγνωρίζεται από ένα ΑΠΑ, τότε το ίδιο ΑΠΑ μπορεί να θεωρηθεί σαν ΜΠΑ, μετατρέποντας κάθε κατάσταση q του ΑΠΑ στο μοναδιαίο σύνολο {q}, που είναι η αντίστοιχη κατάσταση του ΜΠΑ.

Η κατεύθυνση “και μόνο αν” είναι λίγο δυσκολότερη στην απόδειξη, αλλά βασίζεται στην απλή ιδέα οτι, δοσμένου ενός ΜΠΑ το οποίο αναγνωρίζει την L, μπορούμε να κατασκευάσουμε ένα ΑΠΑ που αναγνωρίζει την ίδια L “προσομοιώνοντας” τη λειτουργία του ΜΠΑ σε κάθε χρονική στιγμή, αντιστοιχίζοντας σύνολα καταστάσεων του ΜΠΑ σε καταστάσεις του ΑΠΑ. Δηλαδή, παίρνοντας ένα στιγμιότυπο του ΜΠΑ σε μια χρονική στιγμή, θεωρώντας όλες τις καταστάσεις στις οποίες βρίσκεται κάθε “παράλληλο αντίγραφο” του ΜΠΑ, και βάζοντας αυτές τις καταστάσεις σε ένα σύνολο {q1, ..., qi}, θα πούμε οτι αυτό το σύνολο αντιστοιχεί σε μια μόνο κατάσταση του ισοδύναμου ΑΠΑ. Ας κάνουμε αυτή την ιδέα πιο συγκεκριμένη.

Έστω οτι το M = (Q, Σ, δ, q0, F) είναι ένα ΜΠΑ που αναγνωρίζει την L. Θα κατασκευάσουμε το ΑΠΑ M΄ = (Q΄, Σ, δ΄, q0΄, F΄), ισοδύναμο του Μ, ως εξής.

Οι καταστάσεις του είναι όλα τα υποσύνολα των καταστάσεων του Μ. Δηλαδή, Q΄ = P (Q). (Συνήθως μόνο ένα υποσύνολο, και όχι όλες εκείνες οι καταστάσεις θα χρησιμοποιηθούν από το ΑΠΑ· εντούτοις, εν δυνάμει μπορεί να είναι όλες οι 2|Q| καταστάσεις.) Το είναι το σύνολο όλων των καταστάσεων του που περιέχουν μία q F. Επίσης, q0΄ = {q0}. Θα χρησιμοποιούμε το συμβολισμό [q1, q2, ..., qi] για την κατάσταση q΄ = {q1, q2, ..., qi} του Q΄. Έτσι, μπορούμε τώρα να ορίσουμε τη δ΄:

δ΄([q1, q2, ..., qi], a) = [p1, p2, ..., pj  δ({q1, q2, ..., qi}, a) = {p1, p2, ..., pj}

(Το συμβολίζει τη σχέση ισοδυναμίας, το αν και μόνο αν”.) Έτσι, η δ΄ έχει οριστεί ώστε να δρα κατά τον αναμενόμενοτρόπο, βασιζόμενη στον τρόπο που δρα η δ επί συνόλων καταστάσεων: εφαρμόζοντας τη δ σε καθένα από τα q1, q2, ..., qi με σύμβολο εισόδου a, και σχηματίζοντας την ένωση των καταστάσεων που προκύπτουν, παράγοντας το {p1, p2, ..., pj}. Το τελευταίο είναι μια νέα κατάσταση στο υπό κατασκευή ΑΠΑ, και θα συμβολίζεται με το σύμβολο [p1, p2, ..., pj]. (Σημειώστε οτι εν γένει j i, καθώς το Μ είναι ένα ΜΠΑ, άρα η δ-του μπορεί να δώσει περισσότερες από μια καταστάσεις δοσμένου ενός συμβόλου εισόδου.)

Είναι εύκολο να δείξουμε με επαγωγή επί του μήκους της συμβολοσειράς x οτι:

δ΄(q0΄, x) = [q1, q2, ..., qi  δ(q0, x) = {q1, q2, ..., qi}

Επαγωγική βάση: για | x | = 0 (δηλ. x = ε) έχουμε τετριμμένα οτι δ΄(q0΄, ε) = [q0  δ(q0, ε) = {q0}, αφού [q0] = {q0} εξ ορισμού.

Επαγωγικό βήμα: έστω οτι η υπόθεση ισχύει για εισόδους μήκους n ή μικρότερου. Έστω οτι το xa είναι μια συμβολοσειρά που έχει μήκος n + 1, με a Σ. Τότε:

δ΄(q0΄, xa) = δ΄(δ΄(q0΄, x), a).

Από την επαγωγική υπόθεση,

 δ΄(q0΄, x) = [p1, p2, ..., pj  δ(q0, x) = {p1, p2, ..., pj}.

Αλλά από τον ορισμό της δ΄,

δ΄([p1, p2, ..., pj], a) = [r1, r2, ..., rk  δ({p1, p2, ..., pj}, a) = {r1, r2, ..., rk}.

Οπότε,

δ΄(q0΄, xa) = [r1, r2, ..., rk  δ(q0, xa) = {r1, r2, ..., rk},

πράγμα που ολοκληρώνει το επαγωγικό βήμα.

Για να είναι η απόδειξη πλήρης, πρέπει να προσθέσουμε οτι η δ΄(q0΄, x) ακριβώς όταν η δ(q0, x) περιλαμβάνει μια τελική κατάσταση του Q. Επομένως, L(M) = L(M΄).

Άσκηση 2.3.1: Θεωρήστε το ΜΠΑ που εικονίζεται στον ακόλουθο γράφο:

Αυτό το ΜΠΑ κάνει αποδεκτές όλες τις συμβολοσειρές με πρόθεμα μηδέν ή περισσοτέρων 0 και με κατάληξη το 0 ή το 1. Κάνοντας χρήση της απόδειξης του παραπάνω θεωρήματος 2.3.1, κατασκευάστε ένα ΑΠΑ που να είναι ισοδύναμο με αυτό το ΜΠΑ. Πριν καν ξεκινήσετε, απαντήστε την ερώτηση: ποιο είναι το σύνολο F΄ του ισοδύναμου ΑΠΑ;

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

Άσκηση 2.3.2: Προσπαθήστε να εκφράσετε το ΑΠΑ της άσκησης 2.3.1 με όσο το δυνατόν μικρότερο αριθμό καταστάσεων. Υπόδειξη: θα διαπιστώσετε οτι δεν υλοποιείται με λιγότερες από τρεις καταστάσεις.

Τα ΜΠΑ είναι επίσης χρήσιμα βοηθώντας-μας να καταλάβουμε οτι η προσθήκη μιας φαινομενικά “έξτρα ικανότητας” στο αυτόματο (όπως η ικανότητα να μεταφέρεται σε πολλαπλές καταστάσεις με ένα σύμβολο εισόδου) δεν προσθέτει τίποτα στην υπολογιστική ικανότητα του αυτομάτου. Όταν θα εξετάσουμε τον πιο ισχυρό τύπο αυτομάτων, δηλαδή τις Μηχανές Τούρινγκ, θα διαπιστώσουμε οτι το ίδιο ισχύει και εκεί. Τώρα θα προσθέσουμε άλλη μια ικανότητα στα ΜΠΑ, οπότε θα διαπιστώσουμε το ίδιο πράγμα.

2.4 ΜΠΑ με μεταβάσεις-ε

 

Σ Υ Ν Ε Χ Ι Ζ Ε Τ Α Ι . . .


3. Γραμματικές Χωρίς Συμφραζόμενα

 

 

Σ Υ Ν Ε Χ Ι Ζ Ε Τ Α Ι . . .


Σημειώσεις: (Με κλικ στο ^ επανέρχεστε στο σημείο του κειμένου όπου υπάρχει η αναφορά στην παρούσα υποσημείωση)

^ Τα σημεία, ευθείες, κλπ., λέμε οτι ανήκουν στην “οντολογία” της γεωμετρίας, δηλαδή στο σύνολο εννοιών με τις οποίες ασχολείται η γεωμετρία. Αντίστοιχα, τα σύμβολα (όπως και οι συμβολοσειρές, τα αλφάβητα, οι γλώσσες, κλπ., που ορίζονται αμέσως παρακάτω στο κυρίως κείμενο) αποτελούν την οντολογία της παρούσας θεωρίας.

^ Ας σημειωθεί οτι όροι όπως “πληθάριθμος” (αγγλ.: cardinality) ανήκουν στη θεωρία συνόλων, επομένως στα προαπαιτούμενα του μαθήματος. Το ίδιο ισχύει και για κάθε άλλο όρο του οποίου ο ορισμός δεν δίνεται στο παρόν κείμενο, όπως: “συνάρτηση”, “σχέση”, “ένωση”, “τομή”, κλπ.

^ Δεν χρειάζεται να επαναλαμβάνουμε το «και μόνο αν» από εδώ και μπρος στους ορισμούς. Θυμίζουμε οτι στα μαθηματικά κάθε ορισμός γίνεται αντιληπτός πάντοτε σαν «αν και μόνο αν».

^ Το όνομα αυτό προφέρεται “κλίνι” ή “κλιν” από πρακτικά όλους τους ομιλούντες την αγγλική. Ο ίδιος ο Stephen Cole Kleene όμως πρόφερε το όνομά του ως “κλέινι” (ίδια πηγή), και αυτή η προφορά έχει επικρατήσει (παραδόξως) στην ελληνική απόδοση.

^ Παρόλο που η εποπτική παράσταση των αυτομάτων δεν είναι υποχρεωτική από μαθηματική άποψη, εντούτοις είναι πρακτικά απαραίτητη για την κατανόηση της λειτουργίας ενός αυτομάτου.

^ Ο λόγος που τα δέντρα απεικονίζονται “ανάποδα” (από πάνω προς τα κάτω) είναι προφανής: η ανάγνωση γίνεται από πάνω προς τα κάτω, και το φυσικό σημείο εκκίνησης για την ανάγνωση του διαγράμματος ενός δέντρου είναι η ρίζα-του.

^ Από εδώ και στο εξής θα μιλάμε για ένα ΠΑ που “εικονίζεται” σε ένα διάγραμμα που δείχνει έναν γράφο, με τον οποίο θα υποθέτουμε οτι το αλφάβητο εισόδου αποτελείται μόνο από τα σύμβολα που φαίνονται στον γράφο, και η συνάρτηση μετάβασης δ είναι ακριβώς εκείνη που καθορίζεται από τις ακμές του γράφου.

^ Η έννοια της ισοδυναμίας μεταξύ ΠΑ θα εξεταστεί σε επόμενη ενότητα. Προς το παρόν, άτυπα, μπορούμε να πούμε οτι δύο ΠΑ είναι ισοδύναμα όταν κάνουν αποδεκτό το ίδιο σύνολο συμβολοσειρών (ή “αναγνωρίζουν την ίδια γλώσσα” — όρος που δίνεται αμέσως παρακάτω στο κυρίως κείμενο).

^ Όταν ένα ΜΠΑ υλοποιείται σε υπολογιστή, και ο σκοπός είναι να αποφασίσει την αποδοχή ή απόρριψη μιας δεδομένης συμβολοσειράς εισόδου, τότε — αντίθετα με την αναφερθείσα “ερμηνεία πολλαπλών κόσμων” — πρέπει να είναι παρών ένας μηχανισμός στο πρόγραμμα ώστε αν κάποια από τις παράλληλες διαδικασίες, που καθεμία υλοποιεί ένα αντίγραφο του ΜΠΑ, τερματίσει, να πληροφορήσει τις υπόλοιπες διαδικασίες ώστε να σταματήσουν να τρέχουν. Αυτό είναι απαραίτητο γιατί στους υπολογιστές είναι επιθυμητό τα προγράμματα να σταματούν να τρέχουν όσο το δυνατόν γρηγορότερα. Αλλά αν ο σκοπός είναι να απαριθμηθούν μερικές από τα αποδεκτές συμβολοσειρές της γλώσσας που αναγνωρίζει το αυτόματο, τότε αυτό το σήμα (για να σταματήσουν οι άλλες παράλληλες διαδικασίες) είναι περιττό.


Βιβλιογραφία

  1. Hopcroft, John E., and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison Wesley, Reading, Massachusetts.

  2. Papadimitriou, Christos E. (1994). Computational Complexity. Addison Wesley, Reading, Massachusetts.

  3. Sipser, Michael (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning, Boston, Massachusetts.


Πίσω στη γενική σελίδα του Διαδικτυακού Επιστημονικού Πανεπιστημίου