Πλήρες αυτόματο

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

Πώς κατασκευάζουμε πλήρες αυτόματο

Έστω το εξής αυτόματο A = ⟨Q, Σ, δ, q₀, F⟩:

Εδώ δεν είναι σχεδιασμένη η μετάβαση από την κατάσταση q₀ για το γράμμα «b». Αν συμβεί κάτι τέτοιο, λέμε ότι το αυτόματο δεν αποδέχεται τη δοσμένη λέξη εισόδου. Ωστόσο, από την άποψη του τυπικού ορισμού δεν είναι πάντα βολικό η συνάρτηση μετάβασης δ να μην είναι ορισμένη για κάποιες τιμές· εδώ, για παράδειγμα, δεν είναι ορισμένη η δ(q₀, b).

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

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

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

Ορισμός

Για το πλήρες αυτόματο A = ⟨Q, Σ, δ, q₀, F⟩ ισχύει λοιπόν ότι

$$\mathrm{\forall }q\in Q\mathrm{\forall }a\in \mathrm{\Sigma }\mathrm{\exists }r\in Q:\delta (q,a)=r.$$

Πηγές

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools