7.5 NFA με ε-κινήσεις

Μια ακόμη παραλλαγή του μοντέλου του πεπερασμένου αυτομάτου είναι το μη ντετερμινιστικό αυτόματο με $\epsilon$-κινήσεις. Αυτό είναι ένα NFA που έχει, ενδεχομένως, και κάποιες ακμές που αντί να έχουν ως ετικέτα ένα γράμμα του αλφαβήτου έχουν την κενή λέξη $\epsilon$. Κινούμενοι πάνω στο αυτόματο αυτό για να αναγνωρίσουμε μια λέξη έχουμε το δικαίωμα να διανύσουμε μια $\epsilon$-ακμή οποτεδήποτε υπάρχει μια τέτοια από την τρέχουσα κατάσταση χωρίς να μας ενδιαφέρει ποιο είναι το επόμενο γράμμα της λέξης. Η διάνυση μιας $\epsilon$-ακμής δε συνοδεύεται από μεταπήδηση στο επόμενο γράμμα της λέξης. Ας τα λέμε αυτά $\epsilon$-NFA.

Ορισμός 7.14   (Μη ντετερμινιστικό αυτόματο με $\epsilon$-κινήσεις ($\epsilon$-NFA) ) Ένα μη ντετερμινιστικό αυτόματο με $\epsilon$-κινήσεις ($\epsilon$-NFA) είναι μια πεντάδα

$$(Q, \Sigma, \delta, q_0, F)$$

όπου

• $Q$ είναι ένα πεπερασμένο σύνολο καταστάσεων,
• $\Sigma$ είναι ένα πεπερασμένο αλφάβητο,
• $\delta$ είναι η συνάρτηση μετάβασης (transition function) με πεδίο ορισμού το $Q \times (\Sigma\cup{\left\{{\epsilon}\right\}})$ και πεδίο τιμών το δυναμοσύνολο $2^Q$, το σύνολο δηλ. όλων των υποσυνόλων του $Q$.
• $q_0\in Q$ είναι μια από τις καταστάσεις που ονομάζεται αρχική, και
• $F \subseteq Q$ είναι το σύνολο των τελικών καταστάσεων.

Παρατήρηση 7.8   Η ουσιαστική διαφορά από τον ορισμό του NFA είναι ότι η συνάρτηση μετάβασης μπορεί να έχει και το $\epsilon$ ως δεύτερο όρισμα και όχι απαραίτητα ένα γράμμα του αλφαβήτου $\Sigma$.

Παρατήρηση 7.9   Το νόημα μιας $\epsilon$-ακμής από μια κορυφή $q_1$ σε μια κορυφή $q_2$ είναι το εξής: αν το NFA βρίσκεται στην κατάσταση $q_1$ τότε μπορεί να επιλέξει να μεταβεί στην κατάσταση $q_2$ χωρίς να διαβάσει το επόμενο γράμμα της λέξης.

Ορισμός 7.15   (Αναγνώριση λέξης από $\epsilon$-NFA) Θεωρούμε ότι μια λέξη $w=w_1 w_2 \ldots w_n$, $w_j \in \Sigma$, αναγνωρίζεται από ένα $\epsilon$-NFA αν υπάρχει τρόπος να κινηθούμε, διαβάζοντας το $w$, πάνω στο γράφημα ώστε να καταλήξουμε σε τελική κορυφή. Ξεκινούμε ευρισκόμενοι στην αρχική κατάσταση $q_0$ και διαβάζουμε τα γράμματα $w_1$ έως $w_n$ με αυτή τη σειρά. Σε κάθε βήμα έχουμε τη δυνατότητα να διαβάσουμε το επόμενο γράμμα $w_j$ και να εκτελέσουμε μια μετάβαση σε νέα κατάσταση ή όχι.

Κάθε φορά που διαβάζουμε ένα γράμμα $w_j$, και ευρισκόμενοι στην κατάσταση $q$, επιλέγουμε ως επόμενη κατάσταση μια από τις καταστάσεις του συνόλου $\delta(q,w_j)$. (Αν το σύνολο αυτό είναι κενό η λέξη απορρίπτεται.) Αν επιλέξουμε να μη διαβάσουμε το επόμενο γράμμα της λέξης μπορούμε να μεταβούμε σε νέα κατάσταση ακολουθώντας μια $\epsilon$-ακμή, μπορούμε δηλ. να μεταβούμε σε μια αποιαδήποτε από τις καταστάσεις του συνόλου $\delta(q,\epsilon)$, όπου $q$ είναι η τρέχουσα κατάσταση. (Αν το σύνολο αυτό είναι κενό η λέξη απορρίπτεται.) Είναι φανερό ότι για κάθε λέξη υπάρχουν ενδεχομένως περισσότεροι από ένας τρόποι να κινηθούμε πάνω στο αυτόματο διαβάζοντας τα γράμματα αυτής της λέξης, αφού σε κάθε βήμα ενδέχεται να έχουμε τη δυνατότητα να επιλέξουμε την επόμενή μας κατάσταση. Απορρίπτεται η λέξη $w$ αν και μόνο αν κανείς από τους δυνατούς τρόπους κίνησης δεν καταλήγει σε τελική κορυφή.

Ορισμός 7.16   (Γλώσσα ενός $\epsilon$-NFA) Το σύνολο των λέξεων που αποδέχεται το μη ντετερμινιστικό αυτόματο με $\epsilon$ κινήσεις $M$ ονομάζεται η γλώσσα που αναγνωρίζει το αυτόματο και συμβολίζεται με $L(M)$.

Παράδειγμα 7.22   Το $\epsilon$-NFA του Σχήματος 7.10 αναγνωρίζει τη γλώσσα $0^*1^*2^*$.

Σχήμα 7.10: Ένα $\epsilon$-NFA για τη γλώσσα $0^*1^*2^*$.

Για παράδειγμα, πώς αναγνωρίζει τη λέξη $0^21^32^5$ (συντομογραφία για τη λέξη $0011122222$); Κάνει δύο μεταβάσεις από την πρώτη κορυφή στον εαυτό της διαβάζοντας τα δύο 0, μετά μεταβαίνει στη δεύτερη κορυφή χωρίς να διαβάσει τίποτα, μεταβαίνει από τη δεύτερη κορυφή στον εαυτό της τρεις φορές διαβάζοντας τα 1, μεταβαίνει στην τρίτη κορυφή χωρίς πάλι να διαβάσει τίποτα, και τέλος μεταβαίνει από την τρίτη κορυφή στον εαυτό της διαβάζοντας τα πέντε 2.

Άσκηση 7.22   Κατασκευάστε ένα $\epsilon$-NFA που να αναγνωρίζει τη γλώσσα $(0101)^* \cup (111)^*$.

Άσκηση 7.23   Αν $M_1$ και $M_2$ είναι δύο DFA περιγράψτε πως θα τα χρησιμοποιήσετε αυτά για να κατασκευάσετε ένα $\epsilon$-NFA για τη γλώσσα $L(M_1) \cup L(M_2)$.

Υπόδειξη: Χρησιμοποιήστε τα $M_1$ και $M_2$ βάζοντας πριν από αυτά μια κοινή κατάσταση εισόδου με $\epsilon$-κινήσεις μόνο προς τα δύο DFA.

Άσκηση 7.24   Αν $M_1$ και $M_2$ είναι δύο DFA περιγράψτε πως θα τα χρησιμοποιήσετε αυτά για να κατασκευάσετε ένα $\epsilon$-NFA για τη γλώσσα $L(M_1)L(M_2)$. Αν το $M_1$ έχει ακριβώς μια τελική κατάσταση κατασκευάστε DFA για τη γλώσσα αυτή.

Υπόδειξη: Χρησιμοποιήστε το $M_1$ ακολουθούμενο από το $M_2$. Από τις τελικές καταστάσεις του $M_1$ θα φεύγουν κάποιες $\epsilon$-ακμές.