ART

 

.

Το ντετερμινιστικό πεπερασμένο αυτόματο (deterministic finite state automaton ή DFA) είναι ένα υπολογιστικό μοντέλο, ένας εξιδανικευμένος νοητός υπολογιστής αποτελούμενος από έναν πεπερασμένο αριθμό καταστάσεων και μια συνάρτηση μετάβασης, μέσω της οποίας καθορίζονται οι μεταβάσεις από κατάσταση σε κατάσταση, ανάλογα με την είσοδο που δέχεται το αυτόματο. Η έξοδος του αυτόματου θα είναι είτε αποδοχή είτε απόρριψη της εισόδου.

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

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

Ορισμός

Ένα ντετερμινιστικό πεπερασμένο αυτόματο είναι μια πεντάδα (Q, Σ, δ, q0, F) που αποτελείται από

ένα πεπερασμένο σύνολο καταστάσεων Q
ένα αλφάβητο εισόδου Σ
μια συνάρτηση μετάβασης \( \delta : Q \times \Sigma \rightarrow Q \)
μια αρχικής κατάσταση q0 και
ένα σύνολο τελικών καταστάσεων F, υποσύνολο του Q.

Πεπερασμένο σύνολο καταστάσεων

Πρόκειται για ένα σύνολο πεπερασμένων στον αριθμό καταστάσεων. Το αυτόματο κινείται μεταξύ αυτών των καταστάσεων ξεκινώντας από την αρχική κατάσταση q0. Στο σύνολο πεπερασμένων καταστάσεων εμπεριέχονται η αρχική κατάσταση και οι τελικές καταστάσεις F.
Αλφάβητο εισόδου

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

Η συνάρτηση μετάβασης καθορίζει την επόμενη κατάσταση στην οποία θα μεταβεί το αυτόματο, ανάλογα με το σύμβολο που διαβάζει κάθε φορά.

Η συνάρτηση μετάβασης, δ, έχει ως παραμέτρους την κατάσταση στην οποία βρίσκεται το αυτόματο και το σύμβολο που διαβάζει. Ως έξοδο δίνει μία και μόνο μία κατάσταση. Το πεδίο ορισμού της είναι όλα τα ζεύγη κατάστασης-συμβόλου, Q \times \Sigma, και το πεδίο τιμών της είναι το σύνολο των πεπερασμένων καταστάσεων Q.

Για παράδειγμα, η παράσταση \( \delta (q_1,a) = q_2 \) σημαίνει ότι αν το αυτόματο βρίσκεται στην κατάσταση q1 και διαβάσει το σύμβολο α, θα μεταβεί στην κατάσταση q2.

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

Για παράδειγμα, μια συνάρτηση μετάβασης για την οποία ισχύουν τα εξής:

δ(q0,a) = q0, δ(q0,b) = q1
δ(q1,a) = q1, δ(q1,b) = q0

μπορεί να εκφραστεί με τον πίνακα


a
b
q0 q0 q1
q1 q1 q0

Σύνολο τελικών καταστάσεων

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

Το ντετερμινιστικό πεπερασμένο αυτόματο αρχικά βρίσκεται στην κατάσταση q0, δηλαδή στην αρχική κατάσταση. Διαβάζει το πρώτο σύμβολο της εισόδου και, σύμφωνα με την συνάρτηση μετάβασής του, μεταβαίνει στην αντίστοιχη κατάσταση. Από αυτή την κατάσταση, διαβάζει το επόμενο σύμβολο της εισόδου και πάλι σύμφωνα με την συνάρτηση μετάβασης μεταβαίνει στην επόμενη κατάσταση. Η διαδικασία αυτή επαναλαμβάνεται μέχρι να διαβαστεί όλη η είσοδος από το αυτόματο. Αν το αυτόματο καταλήξει σε τελική κατάσταση, τότε η συμβολοσειρά της εισόδου γίνεται δεκτή. Διαφορετικά, απορρίπτεται.
Παράδειγμα
Παράδειγμα πεπερασμένου ντετερμινιστικού αυτόματου που αναγνωρίζει συμβολοσειρές που τελειώνουν με το σύμβολο b ακολουθούμενο από μηδενικό ή άρτιο αριθμό a συμβόλων

Στο διάγραμμα απεικονίζεται ένα αυτόματο. Οι καταστάσεις του είναι οι q0, q1 και q2. Η αρχική κατάσταση είναι η q0. Το αυτόματο του παραδείγματος έχει μόνο μία τελική κατάσταση, την q1. To αλφάβητο εισόδου αποτελείται από τα σύμβολα a και b. Επομένως,

Q = {q0, q1, q2}
Σ = {a, b}
F = {q1}

Η συνάρτηση μετάβασης είναι η


a
b
q0 q0 q1
q1 q2 q1
q2 q1 q1

Έστω ότι η είσοδος του αυτόματου είναι η συμβολοσειρά aabba. Το αυτόματο αρχικά βρίσκεται στην κατάσταση q0. Διαβάζοντας το πρώτο σύμβολο της συμβολοσειράς, που είναι το a, το αυτόματο θα παραμείνει στην κατάσταση q0. Διαβάζοντας το επόμενο σύμβολο, που είναι πάλι το a, πάλι το αυτόματο μένει στην ίδια κατάσταση. Με το επόμενο σύμβολο b, το αυτόματο μεταβαίνει στην κατάσταση q1. Διαβάζοντας το επόμενο σύμβολο, που είναι πάλι το b, το αυτόματο θα παραμείνει στην εκεί. Και με το τελευταίο σύμβολο της συμβολοσειράς, το αυτόματο θα πάει από την κατάσταση q1 στην q2, η οποία δεν είναι τελική, οπότε η συγκεκριμένη συμβολοσειρά απορρίπτεται.

Με την ίδια διαδικασία, η συμβολοσειρά aabab ή η ababbaa γίνονται αποδεκτές, δηλαδή αναγνωρίζονται από το αυτόματο. Γενικά, το συγκεκριμένο αυτόματο αναγνωρίζει κάθε συμβολοσειρά που τελειώνει με το σύμβολο b ή ακολουθείται από άρτιο αριθμό συμβόλων a. Επομένως, η τυπική γλώσσα που γίνεται αποδεκτή από το αυτόματο του παραδείγματος είναι αυτή που αποτελείται από αυτές τις λέξεις. Ή αλλιώς, το αυτόματο του παραδείγματος αναγνωρίζει την γλώσσα που περιγράφεται από την κανονική έκφραση a*b(b+a(a+b))*. Επειδή η συγκεκριμένη τυπική γλώσσα αναγνωρίζεται από κάποιο ντετερμινιστικό πεπερασμένο αυτόματο (όπως, αυτό του παραδείγματος) είναι κανονική γλώσσα.


Ελαχιστοποίηση

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

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

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

Για την διαδικασία της ελαχιστοποίησης ενός ντετερμινιστικού πεπερασμένου αυτόματου, βοηθάει η χρήση ενός πίνακα στον οποίο σημειώνονται οι συγκρίσεις κάθε ζεύγους καταστάσεων.
Παράδειγμα
Το αρχικό αυτόματο προς ελαχιστοποίηση, που αναγνωρίζει τη γλώσσα 0*10*. Οι διπλά κυκλωμένες καταστάσεις είναι τελικές.

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

b
c X X
d X X
e X X
f X X X
a b c d e

Σε αυτήν την φάση, έχοντας αποκλείσει την ένωση τελικών καταστάσεων με μη τελικές, αυτές που ενδέχεται να συγχωνευθούν (χωρίς να είναι σίγουρο ακόμα, αφού δεν έχει εφαρμοστεί το δεύτερο κριτήριο) είναι οι καταστάσεις στα ζεύγη (a,b), (d,c), (e,c), (e,d), (f,a) και (f,b).

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

Για το ζεύγος (a,b):

Με αφετηρία την κατάσταση "a" και είσοδο το σύμβολο "0", το αυτόματο μεταβαίνει στην κατάσταση "b". Δηλαδή, δ(a,0)=b.
Με αφετηρία την κατάσταση "b" και είσοδο το σύμβολο "0", το αυτόματο μεταβαίνει στην κατάσταση "a". Δηλαδή, δ(b,0)=a.
Έτσι, το ένα παραγόμενο ζεύγος είναι το (b,a).
Με αφετηρία την κατάσταση "a" και είσοδο το σύμβολο "1", το αυτόματο μεταβαίνει στην κατάσταση "c". Δηλαδή, δ(a,1)=c.
Με αφετηρία την κατάσταση "b" και είσοδο το σύμβολο "1", το αυτόματο μεταβαίνει στην κατάσταση "d". Δηλαδή, δ(b,1)=d.
Έτσι, το άλλο παραγόμενο ζεύγος είναι το (c,d).
Και για τα δύο νέα ζεύγη, δεν έχει σημειωθεί ότι οι καταστάσεις τους είναι διακριτές. Επομένως, ούτε το αρχικό ζεύγος (a,b) σημειώνεται.

Για το ζεύγος (d,c):

Με είσοδο το σύμβολο "0", το παραγόμενο ζεύγος είναι το (e,e). Επομένως, και από τις δύο καταστάσεις, το αυτόματο καταλήγει στην ίδια κατάσταση.
Με είσοδο το σύμβολο "1", το παραγόμενο ζεύγος είναι το (f,f). Και από τις δύο καταστάσεις, το αυτόματο μεταβαίνει στην ίδια κατάσταση.
Προφανώς, μία κατάσταση δεν είναι διακριτή από τον εαυτό της. Επομένως, το αρχικό ζεύγος (d,c) δεν σημειώνεται ως ζεύγος με διακριτές μεταξύ τους καταστάσεις.

Το ίδιο ακριβώς συμβαίνει και για τα ζεύγη (e,c) και (e,d). Οπότε, δεν σημειώνονται.

Για το ζεύγος (f,a):

Με είσοδο το "0", το παραγόμενο ζεύγος είναι το (f,b), το οποίο δεν είναι σημειωμένο στον βοηθητικό πίνακα.
Με είσοδο το "1", το παραγόμενο ζεύγος είναι το (f,c), το οποίο είναι σημειωμένο ως ζεύγος με διακριτές καταστάσεις.
Από την στιγμή που, τουλάχιστον με ένα από τα σύμβολα της αλφαβήτου, παράγεται ζεύγος που έχει διακριτές μεταξύ τους καταστάσεις, το αρχικό ζεύγος (f,a) σημειώνεται κι αυτό.

Για το ζεύγος (f,b):

Με είσοδο το "0", το παραγόμενο ζεύγος είναι το (f,a).
Με είσοδο το "1", το παραγόμενο ζεύγος είναι το (f,d).
Εδώ και τα δύο νέα ζεύγη έχουν διακριτές μεταξύ τους καταστάσεις. Επομένως, και οι καταστάσεις f και b είναι διακρίσιμες.

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

b
c X X
d X X
e X X
f Χ Χ X X X
a b c d e

Με την ίδια διαδικασία, το δεύτερο κριτήριο εφαρμόζεται ξανά για τα ζεύγη (d,c), (e,c) και (e,d) που έχουν απομείνει. Διαπιστώνεται ότι κανένα από αυτά τα ζεύγη δεν σημειώνεται και έτσι η φάση του καθορισμού των καταστάσεων που θα συγχωνευθούν τελειώνει.

Από τον πίνακα φαίνεται ότι οι ισοδύναμες καταστάσεις είναι οι a-b, d-c, e-d και e-c. Αφού, η d είναι ισοδύναμη με την c και η c ισοδύναμη με την e, είναι αναμενόμενο (όπως άλλωστε επαληθεύεται) να είναι και η d ισοδύναμη με την e. Στο σύνολο {e,d,c} οι καταστάσεις είναι ανά δύο ισοδύναμες μεταξύ τους. Επομένως, θα συγχωνευθούν και οι τρεις σε μία.
Minimized DFA.jpg

Το νέο ντετερμινιστικό πεπερασμένο αυτόματο του σχήματος, είναι το ελαχιστοποιημένο αυτόματο του προηγούμενου σχήματος.
Βιβλιογραφία

Michael Sipser, Εισαγωγή στη θεωρία υπολογισμού, 2007
Harry R. Lewis - Χρίστος Χ. Παπαδημητρίου, Στοιχεία Θεωρίας Υπολογισμού


Εγκυκλοπαίδεια Πληροφορικής

Κόσμος

Αλφαβητικός κατάλογος

Hellenica World - Scientific Library

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License