Πεπερασμένα αυτόματα (ΠΑ)
Ενα πεπερασμένο αυτόματο (ή μηχανή πεπερασμένων καταστάσεων) είναι μια μηχανή αναγνώρισης γλώσσας.
Περιγράφεται από:
- μία κεντρική μονάδα επεξεργασίας προκαθορισμένης και πεπερασμένης χωρητικότητας
- είσοδο συμβολοσειράς
- έξοδο αποτελέσματος υπολογισμού για το αν η είσοδος είναι αποδεκτή από τη μηχανή
Ντετερμινιστικό (ή αιτιοκρατικό) πεπερασμένο αυτόματο (ΝΠΑ)
Το πεπερασμένο αυτόματο που οι μεταβάσεις του στην επόμενη κατάσταση προσδιορίζονται από την τρέχουσα κατάστασή του και ένα σύμβολο στην είσοδο, λέγεται Ντετερμινιστικό ΠΑ ή Προσδιοριστικό ΠΑ.
Ορισμός (Ντετερμινιστικό πεπερασμένο αυτόματο)
Ένα Ντετερμινιστικό Αυτόματο (Deterministic Finite Automaton ή DFA) είναι ουσιαστικά ένα κατευθυνόμενο γράφημα, του οποίου οι κορυφές K (ή Q) ονομάζονται καταστάσεις (states) και από κάθε κορυφή φεύγει ακριβώς μια ακμή για κάθε γράμμα του αλφαβήτου Σ. Υπάρχει μια διακεκριμένη κατάσταση q0, η αρχική κατάσταση και ένα μη-κενό σύνολο F από τελικές καταστάσεις.
Ενα ντετερμινιστικό πεπερασμένο αυτόματο ορίζεται ως μία πεντάδα
M = (K, Σ, δ, s, F) όπου:
- K (ή Q) είναι ένα πεπερασμένο σύνολο καταστάσεων
- Σ είναι ένα αλφάβητο
- s ∈ K είναι η αρχική κατάσταση
- F ⊆ K είναι το σύνολο των τελικών καταστάσεων και
- δ : K × Σ → K μία συνάρτηση μετάβασης
Η γλώσσα που δέχεται ένα ντεντερμινιστικό ΠΑ δίνεται από το σύνολο των αποδεκτών συμβολοσειρών.
Η γλώσσα που γίνεται δεκτή από το M, συμβολίζεται με L(M) και αποτελείται από το σύνολο των συμβολοσειρών που δέχεται το M.
Συνολική κατάσταση
Ως συνολική κατάσταση της μηχανής ορίζουμε τη θέση της σε μία χρονική στιγμή, δηλ. την εσωτερική κατάσταση του πεπερασμένου ελέγχου και τη θέση της κεφ. ανάγνωσης.
Σε ένα ντεντερμινιστικό ΠΑ M = (K, Σ, δ, s, F) κάθε συνολική κατάσταση είναι στοιχείο του K x Σ*.
Ο υπολογισμός που εκτελεί ένα ΠΑ δίνεται ως ακολουθία συνολικών καταστάσεων.
Κανόνες για ΝΠΑ
Ισχύουν οι παρακάτω γενικοί κανόνες
- Η μετάβαση από μια κατάσταση Χ σε μια επόμενη είναι καθορισμένη (για δεδομένη είσοδο)
- Υπάρχει πάντα μόνο μία επόμενη κατάσταση (για δεδομένη είσοδο)
- Δεν υπάρχει μετάβαση τυχαία ή αυθαίρετη
- Η είσοδος σε μια κατάσταση είναι ένα στοιχείο του αλφάβητου Σ
- Ένα ΝΠΑ είναι εύκολο να σχεδιαστεί
Εστω το ντετερμινιστικό πεπερασμένο αυτόματο M, όπου:
K = {q0, q1}
Σ = {0, 1}
s = q0
F = {q0}
και η συνάρτηση μετάβασης:
q σ δ(q, σ) --------------- q0 0 q0 q0 1 q1 q1 0 q1 q1 1 q0
Να ελεγχθεί αν η συμβολοσειρά 0110 είναι δεκτή.
Οι μεταβάσεις είναι:
δ(q0, 0) = q0 δ(q0, 1) = q1 δ(q1, 0) = q1 δ(q1, 1) = q0
Διάγραμμα καταστάσεων - μεταβάσεων
Διάγραμμα καταστάσεων - μεταβάσεων είναι ένα κατευθυνόμενο γράφημα με επιγραφές στα τόξα (μεταβάσεις) που συνδέουν τους κόμβους (καταστάσεις).
Η συνάρτηση μετάβασης για ένα ΠΑ δίνεται από ένα διάγραμμα καταστάσεων - μεταβάσεων, όπου κάθε δ(q, a) = q0 αναπαριστάται από ένα τόξο με επιγραφή a από τον κόμβο q στον κόμβο q0.
Οι τελικές καταστάσεις σημειώνονται με διπλό περίγραμμα και η αρχική με ένα > ή →
Εστω Μ το παρακάτω ΝΠΑ.
| K | = | {q0, q1} |
| Σ | = | {0, 1} |
| s | = | q0 |
| F | = | {q0} |
και η συνάρτηση μετάβασης
| q | σ | δ(q, σ) |
|---|---|---|
| q0 | q0 | q0 |
| q0 | 1 | q1 |
| q1 | 0 | {q1} |
| q1 | 1 | {q0} |
Το διάγραμμα είναι:
Να σχεδιαστεί το M για την:
L(M) = {ω : ω ∈ {0, 1}* : ω δεν έχει δύο συνεχόμενα 1}
Όταν για το Μ ισχύει:
K = {q0, q1, q2}
Σ = {0, 1}
s = q0
F = {q0, q1}
Το διάγραμμα είναι:
και η συνάρτηση μετάβασης (ή πίνακας καταστάσεων - μεταβάσεων):
q σ δ(q, σ) --------------- q0 0 q0 q0 1 q1 q1 0 q0 q1 1 q2 q2 0 q2 q2 1 q2
Η q2 ονομάζεται κατάσταση καταβόθρα (trap) γιατί όταν προσεγγίζεται ο υπολογισμός εγκλωβίζεται σ' αυτήν ανεξάρτητα από το υπόλοιπο της συμβολοσειράς.
Να σχεδιαστεί ένα αυτόματο με Σ = {0, 1} που δέχεται συμβολοσειρές που αρχίζουν με 1 και τελειώνουν με 0.
Το διάγραμμα είναι:
Να σχεδιαστεί ένα αυτόματο με Σ = {0, 1} που δέχεται μόνο τη συμμβολοσειρά 101.
Το διάγραμμα είναι:
Πρέπει να συμπληρωθεί.
Να σχεδιαστεί ένα αυτόματο με Σ = {0, 1} που δέχεται μόνο τη συμμβολοσειρά 0011.
Το διάγραμμα είναι:
Να σχεδιαστεί ένα αυτόματο με Σ = {0, 1} που ΔΕΝ δέχεται τη συμβολοσειρά 0011.
Το διάγραμμα είναι:
Παρατηρήστε ότι το πρώτο διάγραμμα με το δεύτερο διαφέρουν μόνο στην τελικές καταστάσεις. Δηλαδή στο δεύτερο διάγραμμα οι τελικές γίνονται μη τελικές και οι μη τελικές τελικές.
Να σχεδιαστεί αυτόματο με Σ = {0, 1} με άρτιο αριθμό 0 και άρτιο αριθμό 1.
Το διάγραμμα είναι:
Από το παρακάτω διάγραμμα να βρεθούν ποιές συμβολοσειρές είναι δεκτές και ποιές όχι.
0, 00, 11, 111, 010, 101, 1, 011, 1001, 011
Το διάγραμμα είναι:
ΝΠΑ που αποτελεί μοντέλο ανελκυστήρα για τρεις ορόφους:
Να σχεδιαστεί αυτόματο που θα αναγνωρίζει τη γλώσσα L εκείνων των λέξεων του Σ = {0, 1} που έχουν μέσα το πολύ δύο διαδοχικά 1. Ισοδύναμα, είναι εκείνες οι λέξεις στις οποίες δεν εμφανίζεται η μορφή 111.
Να σχεδιαστεί ένα DFA που αναγνωρίζει εκείνες τις λέξεις πάνω από το Σ = {0, 1} που έχουν μήκος τουλάχιστον 5 και το 5ο γράμμα τους από τα αριστερά είναι 1.
Να σχεδιαστεί ένα DFA που αναγνωρίζει εκείνες τις λέξεις πάνω από το Σ = {0, 1} που περιέχουν τρία διαδοχικά 0.
Να σχεδιαστεί ένα DFA που αναγνωρίζει εκείνες τις λέξεις πάνω από το Σ = {0, 1} που τελειώνουν σε 00.
Να σχεδιαστεί ένα DFA που αναγνωρίζει εκείνες τις λέξεις πάνω από το Σ = {a, b} που αρχίζουν από ab.
Να σχεδιαστεί αυτόματο που θα αναγνωρίζει τη γλώσσα a{bb}*bc, δηλ. όλες εκείνες τις λέξεις στο αλφάβητο Σ = {a, b} που αρχίζουν με a, ακολουθούν 0 ή περισσότερες λέξεις bb, και τελειώνουν με τη λέξη bc.