Πεπερασμένο αυτόματο

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

Παράδειγμα

Άτυπα θα περιγράψουμε το πεπερασμένο αυτόματο με ένα διάγραμμα καταστάσεων, που περιγράφει το πεπερασμένο αυτόματο:

Παράδειγμα ενός απλού πεπερασμένου αυτομάτου

Το αυτόματο αποτελείται από καταστάσεις· στο σχήμα είναι οι τρεις στρογγυλές καταστάσεις q₀, q₁ και q₂. Ανάμεσα σε αυτές τις καταστάσεις υπάρχουν μεταβάσεις, δηλαδή τα βέλη. Στο αυτόματο πρέπει επίσης να υπάρχει αρχική κατάσταση, εδώ η κατάσταση q₀. Την αρχική κατάσταση τη σχεδιάζουμε συχνά έτσι, ώστε προς αυτήν να κατευθύνεται ένα βέλος που δεν ξεκινά από καμία κατάσταση. Επιπλέον, στο αυτόματο υπάρχει συνήθως τελική κατάσταση, που τη σχεδιάζουμε με διπλή γραμμή, οπότε στο σχήμα είναι η κατάσταση q₂.

Ένα αυτόματο που έχει κατασκευαστεί έτσι αποδέχεται ορισμένες λέξεις. Δίνουμε δηλαδή στο αυτόματο κάποιες λέξεις και το αυτόματο προσπαθεί να τις αποδεχτεί. Αν τις αποδεχτεί, το αυτόματο απαντά ΝΑΙ, αν δεν τις αποδεχτεί, απαντά ΟΧΙ. Το αυτόματό μας προσπαθεί να αποδεχτεί λέξεις που αποτελούνται από τα γράμματα «a, b, c», οπότε μπορούμε να δοκιμάσουμε να αποδεχτούμε τη λέξη «abbc».

Ξεκινάμε από την αρχική κατάσταση q₀ και στην είσοδο έχουμε τη λέξη «abbc». Στη συνέχεια ακολουθούμε τα βέλη.

Τη λέξη τη διατρέχουμε κλασικά από αριστερά προς τα δεξιά, δηλαδή πρώτο θα πάρουμε το σύμβολο «a». Το βέλος για είσοδο «a» πηγαίνει στην κατάσταση q₁, οπότε πηγαίνουμε εκεί και αφαιρούμε το σύμβολο «a» από τη λέξη. Στην είσοδο έχουμε τη λέξη «bbc»:

Το βέλος για είσοδο «b» κατευθύνεται πίσω στον κόμβο q₁. Ξανά αφαιρούμε το πρώτο γράμμα και στην είσοδο έχουμε τη λέξη «bc». Ξανά παραμένουμε στην κατάσταση q₁. Τέλος έχουμε στην είσοδο τη λέξη «c». Από την κατάσταση q₁ το βέλος για είσοδο «c» μας στέλνει στην κατάσταση q₂.

Έχουμε πια εξαντλήσει όλα τα γράμματα της λέξης εισόδου και βρισκόμαστε στην κατάσταση q₂, που είναι τελική κατάσταση. Αυτό το πεπερασμένο αυτόματο αποδέχεται λοιπόν τη λέξη «abbc».

Αν στο τέλος δεν βρισκόμασταν σε τελική κατάσταση, το αυτόματο δεν θα αποδεχόταν τη λέξη. Το ίδιο θα συνέβαινε και αν σε κάποια κατάσταση δεν είχαμε πού να πάμε. Για παράδειγμα, για είσοδο «ab» θα φτάναμε στην κατάσταση q₁ και εκεί θα τελειώναμε – το αυτόματο δεν αποδέχεται τέτοια λέξη. Αν δοκιμάζαμε τη λέξη «aabbc», πάλι δεν θα είχαμε τύχη, επειδή από την κατάσταση q₁ δεν οδηγεί βέλος για το γράμμα «a».

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

Ορισμός του πεπερασμένου αυτομάτου

Την προηγούμενη διαισθητική εικόνα για το τι είναι πεπερασμένο αυτόματο πρέπει να την τυποποιήσουμε, για να μπορούμε να δουλεύουμε με τα αυτόματα καλύτερα.

Λέμε ότι ένα πεπερασμένο (ντετερμινιστικό) αυτόματο είναι μια πεντάδα ⟨Q, Σ, δ, q₀, F⟩, όπου

Q είναι ένα πεπερασμένο σύνολο καταστάσεων,
Σ (κεφαλαίο σίγμα) είναι το αλφάβητο (πεπερασμένο σύνολο συμβόλων/γραμμάτων),
δ: Q × Σ ⟶ Q είναι η συνάρτηση μετάβασης,
q₀ ∈ Q είναι η αρχική κατάσταση,
F ⊆ Q είναι το σύνολο των τελικών (αποδεκτών) καταστάσεων.

Αν επιστρέψουμε στο προηγούμενο αυτόματο,

μπορούμε να πούμε ότι στο σύνολο καταστάσεων Q υπάρχουν τρεις καταστάσεις Q = {q₀, q₁, q₂}. Το αλφάβητο Σ περιέχει τα γράμματα από τα οποία μπορούμε να σχηματίζουμε λέξεις, τις οποίες το αυτόματο θα αποδέχεται ή θα απορρίπτει. Εδώ πιθανότατα θα είναι το αλφάβητο Σ= {a, b, c}, αλλά μπορεί να είναι και ένα οποιοδήποτε υπερσύνολο αυτού. Η αρχική κατάσταση q₀ είναι η κατάσταση q₀, εδώ δεν αλλάζει τίποτα. Το σύνολο των τελικών καταστάσεων έχει σε αυτό το αυτόματο μόνο μία κατάσταση F = {q₂}.

Ως συνάρτηση μετάβασης εννοούμε τότε εκείνα τα τρία βέλη με τα γράμματα. Αν σε μπερδεύει ο συμβολισμός δ: Q × Σ ⟶ Q, σημαίνει απλώς ότι η δ είναι μια συνάρτηση (ίσως καλύτερα απεικόνιση), που παίρνει δύο παραμέτρους: μια κατάσταση από το Q και ένα γράμμα από το Σ. Μετά την κλήση της συνάρτησης επιστρέφει μια νέα κατάσταση. Τη συνάρτηση μετάβασής μας θα μπορούσαμε να την ορίσουμε με πίνακα ως εξής:

$\begin{array}{ccc} Q & Σ & \to Q \\ q_{0} & a & q_{1} \\ q_{1} & b & q_{1} \\ q_{1} & c & q_{2} \end{array}$

Αν λοιπόν καλέσουμε την δ(q₁, c), εφαρμόζουμε την τρίτη γραμμή και η συνάρτηση απαντά με την κατάσταση q₂ – όπως ακριβώς και το διάγραμμα. Αν βρισκόμαστε στην κατάσταση q₁ και στην είσοδο έχουμε το γράμμα «c», τότε φτάνουμε στην κατάσταση q₂. Πριν ορίσουμε τυπικά τι σημαίνει ότι το αυτόματο αποδέχεται μια λέξη, θα χρησιμοποιήσουμε τη διαισθητική κατανόηση αυτής της έννοιας και θα δούμε μερικά ακόμη παραδείγματα.

Περισσότερα παραδείγματα

Κατασκεύασε ένα αυτόματο που δουλεύει πάνω από δυαδικό αλφάβητο, δηλαδή Σ= {0, 1}, και αποδέχεται μόνο λέξεις που τελειώνουν σε άσο. Π.χ. αποδέχεται τις λέξεις 1, 01, 000001, 0101011.

Το αυτόματό μας έχει δύο καταστάσεις – την αρχική q₀ και την τελική q₁. Όποτε έχουμε στην είσοδο το ψηφίο 1, πηγαίνουμε στην τελική κατάσταση q₁ και παραμένουμε σε αυτήν. Αντίθετα, αν στην είσοδο είναι το ψηφίο 0, πηγαίνουμε στη μη τελική κατάσταση q₀ και επίσης παραμένουμε σε αυτήν.
Κατασκεύασε ένα αυτόματο πάνω από δυαδικό αλφάβητο, που αποδέχεται μόνο λέξεις των οποίων το αρχικό γράμμα είναι διαφορετικό από το τελικό γράμμα.

Το αυτόματο χωρίζεται αμέσως στο πρώτο βήμα σε δύο «υποαυτόματα». Αν η λέξη αρχίζει με μηδέν, το αυτόματο μπαίνει στο αριστερό μέρος και μένει εκεί, αν αρχίζει με άσο, μεταφέρεται στο δεξί μέρος. Μετά είναι πια κλασική περίπτωση: αν βρισκόμαστε στο αριστερό μέρος και στην είσοδο είναι 1, πηγαίνουμε στην τελική κατάσταση και μένουμε εκεί. Αν στην είσοδο είναι 0, πηγαίνουμε στην κατάσταση q₁, η οποία δεν είναι τελική.

Σε αντίθεση με τα προηγούμενα αυτόματα, αυτό το αυτόματο έχει περισσότερες τελικές καταστάσεις, δηλαδή F = {q₃, q₄}.
Κατασκεύασε ένα αυτόματο πάνω από δυαδικό αλφάβητο, που αποδέχεται μόνο λέξεις που δεν περιέχουν δύο μηδενικά στη σειρά.

Αυτό το αυτόματο είναι ενδιαφέρον για δύο λόγους: ο πρώτος είναι ότι αποδέχεται την κενή λέξη. Στο αυτόματο μπορούμε να δοκιμάσουμε να βάλουμε την κενή λέξη και το αυτόματο θα τη δεχτεί, αν η αρχική κατάσταση είναι ταυτόχρονα τελική κατάσταση, κάτι που συνέβη σε αυτό το αυτόματο. Επειδή η κενή λέξη είναι λέξη που δεν περιέχει δύο μηδενικά στη σειρά, αυτό είναι το σωστό. Ο άλλος αξιοσημείωτος λόγος είναι ότι αυτό το αυτόματο έχει όλες τις καταστάσεις τελικές. Η μοναδική περίπτωση στην οποία το αυτόματο δεν θα αποδεχόταν μια λέξη είναι όταν από κάποια κατάσταση δεν οδηγούσε καμία μετάβαση. Αυτό συμβαίνει στην κατάσταση q₁, που δεν έχει μετάβαση για το 0, επειδή τότε η λέξη θα περιείχε δύο μηδενικά στη σειρά.
Κατασκεύασε ένα αυτόματο πάνω από το αλφάβητο {-,+,.,0,1,…,9}, που αποδέχεται μόνο λέξεις που παριστάνουν αριθμό. Αυτό σημαίνει είτε ακέραιο αριθμό, όπως π.χ. 2, 548, 98263, είτε δεκαδικό αριθμό, όπως π.χ. 5584.48, 3.14, και τα δύο και στην εκδοχή για αρνητικό αριθμό με πρόσημο μείον -2, -548, -3.14 και επίσης με ρητά γραμμένο συν, δηλαδή +2, +548, +3.14. Ταυτόχρονα πρέπει να μπορούμε να γράψουμε τον αριθμό 0.123 και ως .123 (χωρίς το μηδέν στην αρχή), και μάλιστα με τα δύο πρόσημα. Θα εισαγάγουμε βοηθητικό συμβολισμό: αντί να γράφουμε δέκα μεταβάσεις για τα δέκα ψηφία, θα χρησιμοποιούμε το σύμβολο N.
Κατασκεύασε ένα αυτόματο πάνω από δυαδικό αλφάβητο, που δέχεται μόνο λέξεις της μορφής 0ⁿ1ⁿ, δηλαδή λέξεις που έχουν στην αρχή ένα ορισμένο πλήθος μηδενικών και ακολουθεί το ίδιο πλήθος άσων. Παραδείγματα τέτοιων λέξεων είναι 0011, 00001111, 01.

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

Τυποποίηση του υπολογισμού του αυτομάτου

Έχουμε ήδη ορίσει τυπικά το ίδιο το πεπερασμένο αυτόματο. Πρέπει ακόμη να ορίσουμε τι κάνει ένα τέτοιο αυτόματο, δηλαδή να ορίσουμε τον υπολογισμό του αυτομάτου.

Διαμόρφωση του αυτομάτου: Λέμε ότι ένα ζεύγος ⟨q, w⟩ ∈ Q × Σ^∗ είναι διαμόρφωση του αυτομάτου, όπου q είναι η τρέχουσα κατάσταση στην οποία βρίσκεται το αυτόματο και w είναι το μέρος της λέξης που δεν έχει διαβαστεί ακόμη. Το Σ^∗ δηλώνει την κλειστότητα Kleene του αλφαβήτου Σ, το σύνολο όλων των λέξεων που μπορούν να σχηματιστούν από τα γράμματα του αλφαβήτου Σ. Στην κλειστότητα ανήκει και η κενή λέξη, που τη συμβολίζουμε ε.

Αν έχουμε αυτόματο ⟨Q, Σ, δ, q₀, F⟩ και προσπαθούμε να αποδεχτούμε τη λέξη w, τότε το αυτόματο βρίσκεται στην αρχική διαμόρφωση ⟨q₀, w⟩. Αν επιστρέψουμε στο αυτόματο

και θέλουμε να αποδεχτούμε τη λέξη w = abbc, τότε η αρχική διαμόρφωση θα είναι ⟨q₀, abbc⟩.

Βήμα υπολογισμού ορίζουμε ως σχέση ↦ ανάμεσα στα σύνολα (Q × Σ^∗) × (Q × Σ^∗), δηλαδή ανάμεσα σε διαμορφώσεις του αυτομάτου. Έστω ότι w = w₀w₁… w_n παριστάνει το μέρος της λέξης w που δεν έχει διαβαστεί ακόμη. Τότε λέμε ότι τα ζεύγη ⟨q₁, w₀w₁… w_n⟩ και ⟨q₂, w₁… w_n⟩ βρίσκονται στη σχέση ↦, το γράφουμε ως

$⟨ q_{1}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{2}, w_{1} \dots w_{n} ⟩,$

αν και μόνο αν δ(q₁, w₀) = q₂. Αν επιστρέψουμε στο παράδειγμά μας, η αρχική διαμόρφωση είναι ⟨q₀, abbc⟩. Από το διάγραμμα βλέπουμε ότι για είσοδο «a» μπορούμε να προχωρήσουμε στην κατάσταση q₁. Μπορούμε έτσι να γράψουμε

$⟨ q_{0}, a b b c ⟩ \mapsto ⟨ q_{1}, b b c ⟩,$

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

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

$K_{1} \mapsto K_{11} \mapsto K_{12} \mapsto K_{13} \mapsto \dots \mapsto K_{2}$

Για παράδειγμα, στο αυτόματό μας ισχύει ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, επειδή αν εκτελέσουμε δύο βήματα υπολογισμού, θα μας μείνει η λέξη «bc» και θα παραμείνουμε στην κατάσταση q₁. Δηλαδή υπάρχει αυτή η ακολουθία διαμορφώσεων:

$⟨ q_{0}, a b b c ⟩ \mapsto ⟨ q_{1}, b b c ⟩ \mapsto ⟨ q_{1}, b c ⟩$

Το αυτόματο αποδέχεται τη λέξη w αν και μόνο αν υπάρχει q_f ∈ F τέτοιο ώστε $⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩$ Αυτό σημαίνει ότι το αυτόματο αποδέχεται τη λέξη w αν και μόνο αν υπάρχει κάποια ακολουθία βημάτων υπολογισμού τέτοια ώστε στο τέλος αυτής της ακολουθίας να έχουμε διαβάσει ολόκληρη τη λέξη και να βρισκόμαστε σε τελική κατάσταση του αυτομάτου. Ότι έχουμε διαβάσει ολόκληρη τη λέξη εκφράζεται με το ότι στη διαμόρφωση στη θέση της λέξης βρίσκεται το ε, δηλαδή η κενή λέξη. Το αυτόματό μας αποδέχεται τη λέξη abbc, επειδή υπάρχει αυτή η ακολουθία διαμορφώσεων:

$⟨ q_{0}, a b b c ⟩ \mapsto ⟨ q_{1}, b b c ⟩ \mapsto ⟨ q_{1}, b c ⟩ \mapsto ⟨ q_{1}, c ⟩ \mapsto ⟨ q_{2}, ε ⟩$

και η κατάσταση q₂ είναι τελική κατάσταση, q₂ ∈ F.

Γλώσσα που αποδέχεται το αυτόματο είναι το σύνολο όλων των λέξεων που το αυτόματο αποδέχεται. Τη γλώσσα του αυτομάτου A θα τη συμβολίζουμε L(A). Ισχύει λοιπόν L(A) ⊆ Σ^∗ και

$L (A) = {w \in Σ^{*} | A αποδέχεται τη λέξη w}$

Κανονική γλώσσα είναι μια γλώσσα που την αποδέχεται κάποιο πεπερασμένο αυτόματο.

Δύο πεπερασμένα αυτόματα είναι ισοδύναμα αν αποδέχονται την ίδια γλώσσα. Δηλαδή τα αυτόματα A₁ και A₂ είναι ισοδύναμα, αν ισχύει L(A₁) = L(A₂).

Πηγές

Κεφάλαια: Πεπερασμένο αυτόματο, Πλήρες αυτόματο, Μη ντετερμινιστικό πεπερασμένο αυτόματο, Προσομοίωση NFA, Μετατροπή NFA σε DFA

« Προηγούμενο: Τυπικές γλώσσες

Επόμενο: Πλήρες αυτόματο »