Πώς μπορεί κανείς να αποδείξει ότι μια γλώσσα είναι τακτική;

Υπάρχουν διάφοροι τρόποι για να αποδειχθεί ότι μια γλώσσα είναι τακτική. Ακολουθεί μια ανάλυση των κοινών μεθόδων, μαζί με εξηγήσεις και παραδείγματα:

1. Κατασκευή ενός πεπερασμένου αυτοματοποιημένου (FA) ή ντετερμινιστικής πεπερασμένης Automaton (DFA)

* Επεξήγηση: Εάν μπορείτε να χτίσετε ένα DFA ή NFA (μη -nondeterministic Finite Automaton) που δέχεται * όλα * και * μόνο * τις χορδές στη γλώσσα, τότε η γλώσσα είναι τακτική.

* Πώς να το κάνετε:

* Καθορίστε τις καταστάσεις: Οι καταστάσεις της FA σας αντιπροσωπεύουν τη "μνήμη" του τι έχει δει μέχρι στιγμής στη συμβολοσειρά εισόδου. Σκεφτείτε ποιες πληροφορίες είναι απαραίτητες για να θυμηθείτε να προσδιορίσετε εάν η συμβολοσειρά είναι στη γλώσσα.

* Καθορίστε τις μεταβάσεις: Οι μεταβάσεις υπαγορεύουν τον τρόπο με τον οποίο η FA μετακινείται από κατάσταση σε κράτος με βάση τα σύμβολα εισόδου. Βεβαιωθείτε ότι οι μεταβάσεις σας αντικατοπτρίζουν σωστά τους κανόνες της γλώσσας.

* Καθορίστε την κατάσταση εκκίνησης: Όπου αρχίζει η επεξεργασία του Automaton.

* Καθορίστε τις καταστάσεις αποδοχής: Τα κράτη που υποδεικνύουν ότι η συμβολοσειρά βρίσκεται στη γλώσσα.

* Παράδειγμα: Εξετάστε τη γλώσσα l ={χορδές πάνω από {a, b} που περιέχουν "ab" ως υποσύνολο}.

`` `

Κράτη:q0 (start), q1, q2 (αποδοχή)

Μεταβάσεις:

- Q0, a -> q1 (βλέπει ένα 'a' μέχρι στιγμής, ενδεχομένως οδηγώντας σε "ab")

- Q0, B -> Q0 (παρατηρείται Α 'Β', Επαναφορά)

- Q1, a -> q1 (βλέπε 'aa' μέχρι στιγμής, εξακολουθεί να ψάχνει για "ab")

- Q1, b -> q2 (βλέπε 'ab'!)

- Q2, a -> q2 (ήδη φαίνεται 'ab', οπότε οποιαδήποτε περαιτέρω είσοδος μας κρατά δεχόμενοι)

- Q2, B -> Q2 (ήδη φαίνεται «AB», οπότε οποιαδήποτε περαιτέρω είσοδος μας κρατάει να δεχόμαστε)

Εκκίνηση κατάστασης:q0

Αποδοχή κατάστασης:Ε2

`` `

Μπορείτε να σχεδιάσετε ένα διάγραμμα κατάστασης για να απεικονίσετε αυτό το FA.

2. Κατασκευή κανονικής έκφρασης

* Επεξήγηση: Εάν μπορείτε να γράψετε μια κανονική έκφραση που περιγράφει * όλα * και * μόνο * τις χορδές στη γλώσσα, τότε η γλώσσα είναι τακτική.

* Πώς να το κάνετε:

* Κατανόηση των βασικών χειριστών κανονικής έκφρασης:

* Concatenation:`ab` (ταιριάζει με τη συμβολοσειρά" ab ")

* Ένωση (ή):`a | b` (ταιριάζει" a "ή" b ")

* Kleene Star (μηδέν ή περισσότερες επαναλήψεις):`a*` (αντιστοιχίες "," a "," aa "," aaa ", ...)

* Kleene Plus (μία ή περισσότερες επαναλήψεις):`a+` (αντιστοιχεί "a", "aa", "aaa", ...)

* Παρενθέσεις για ομαδοποίηση:`(a | b) c` (αντιστοιχεί" ac "ή" bc ")

* Κατηγορίες χαρακτήρων:`[ABC]` (ταιριάζει 'Α', 'Β' ή 'C')

* Ranges:`[a-z]` (ταιριάζει με οποιοδήποτε πεζά γράμμα)

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

* Παράδειγμα: Χρησιμοποιώντας την ίδια γλώσσα l ={χορδές πάνω από {a, b} που περιέχουν "ab" ως υποσύνολο}.

Η κανονική έκφραση είναι:`(a | b)*ab (a | b)*`

* `(a | b)*` σημαίνει μηδέν ή περισσότερα περιστατικά 'a' ή 'b' (οποιαδήποτε σειρά των 'a's και' b).

* `ab` είναι το απαιτούμενο υπόστρωμα.

* `(a | b)*` Και πάλι επιτρέπει οποιαδήποτε σειρά των 'a και' b* μετά* "ab".

3. Χρησιμοποιώντας ιδιότητες κλεισίματος των κανονικών γλωσσών

* Επεξήγηση: Οι τακτικές γλώσσες κλείνουν υπό ορισμένες επιχειρήσεις. Αυτό σημαίνει ότι εάν εφαρμόσετε αυτές τις λειτουργίες σε τακτικές γλώσσες, το αποτέλεσμα είναι επίσης μια κανονική γλώσσα. Οι κοινές ιδιότητες κλεισίματος περιλαμβάνουν:

* Ένωση

* Συγκόλληση

* Αστέρι Kleene

* Διασταύρωση

* Συμπλήρωση

* Διαφορά

* Αντιστροφή

* Ομομορφισμός (υποκατάσταση)

* Πώς να το κάνετε:

1. Δείξτε ότι η γλώσσα μπορεί να κατασκευαστεί από απλούστερες, γνωστές κανονικές γλώσσες χρησιμοποιώντας λειτουργίες κλεισίματος.

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

* Παράδειγμα: Έστω L1 ={χορδές πάνω από {a, b} ξεκινώντας με 'a'} και l2 ={χορδές πάνω από {a, b} τελειώνοντας με 'b'}. Τόσο το L1 όσο και το L2 είναι τακτικοί (μπορείτε εύκολα να γράψετε τακτικές εκφράσεις γι 'αυτούς:`a (a | b)*` και `(a | b)*b`).

Τώρα, εξετάστε τη γλώσσα l =l1 ∩ l2 ={χορδές πάνω από {a, b} ξεκινώντας με 'a' * και * τελειώνοντας με 'b'}.

Δεδομένου ότι οι κανονικές γλώσσες είναι κλειστές κάτω από τη διασταύρωση, το L είναι επίσης τακτικό. Η κανονική του έκφραση είναι `a (a | b)*b`.

4. Θεώρημα myhill-nerode

* Επεξήγηση: Το θεώρημα Myhill-Nerode παρέχει μια απαραίτητη και επαρκή προϋπόθεση για μια γλώσσα να είναι τακτική. Δηλώνει ότι μια γλώσσα L είναι τακτική εάν και μόνο αν έχει πεπερασμένο αριθμό *διακριτών επιθημάτων *. Δύο επίθετα *x *και *y *διακρίνονται σε σχέση με το *l *αν υπάρχει μια συμβολοσειρά *z *έτσι ώστε ακριβώς ένα από τα *xz *ή *yz *είναι σε *l *. Με απλούστερους όρους:Μια γλώσσα L είναι τακτική εάν μπορείτε να διαιρέσετε όλα τα πιθανά προθέματα σε έναν πεπερασμένο αριθμό τάξεων ισοδυναμίας.

* Πώς να το κάνετε (πιο προηγμένο):

1. Καθορίστε μια σχέση ισοδυναμίας που βασίζεται σε διακριτά επιθήματα:`x ≡ y` αν και μόνο αν για όλες τις χορδές` z`, `xz ∈ l` αν και μόνο αν` yz ∈ L`.

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

* Παράδειγμα: Έστω l ={0 n 1 n | n ≥ 0}. Αυτή είναι μια * μη κανονική * γλώσσα (που χρησιμοποιείται για να αποδείξει το λεμλά της άντλησης). Για να κατανοήσουμε διαισθητικά την εφαρμογή Myhill-Nerode:

Εξετάστε τα προθέματα 0, 00, 000, .... αν ήταν κανονικά, τότε τελικά δύο προθέματα, πείτε 0 i και 0 j (όπου θα έπρεπε να είναι ισοδύναμο. Αλλά δεν είναι. Εάν προσαρμόζετε 1 i σε 0 i Παίρνετε 0 i 1 i , το οποίο * είναι * στο L. Ωστόσο, αν προσθέσετε 1 i σε 0 j Παίρνετε 0 j 1 i , που δεν είναι * στο l (επειδή j> i). Έτσι, 0 i και 0 j διακρίνονται. Δεδομένου ότι μπορείτε να δημιουργήσετε έναν άπειρο αριθμό διακριτών προθέσεων, η γλώσσα δεν είναι τακτική. Το θεώρημα Myhill-Nerode χρησιμοποιείται συχνά για να αποδείξει ότι μια γλώσσα δεν είναι * κανονική.

5. Το λεμόνι άντλησης για κανονικές γλώσσες (για να αποδείξει ότι μια γλώσσα δεν είναι * κανονική)

* Επεξήγηση: Το λεμόνι άντλησης είναι ένα εργαλείο για να αποδείξει ότι μια γλώσσα δεν είναι * κανονική. Δηλώνει ότι εάν η γλώσσα L είναι κανονική, τότε υπάρχει μήκος άντλησης *p *(ακέραιος), έτσι ώστε κάθε συμβολοσειρά *s *σε l με μήκος μεγαλύτερο ή ίσο με *p *να μπορεί να χωριστεί σε τρία υποσύνολα, *x *, *y *και *z *, όπου *s *=*xyz *, και οι ακόλουθες συνθήκες κρατούν:

1. Για κάθε i> =0, xy i Το z είναι στο L. (μπορείτε να "αντλήσετε" το μέρος y κάθε φορά και το αποτέλεσμα είναι ακόμα στη γλώσσα).

2. | Y |> 0 (το "αντλημένο" μέρος y πρέπει να έχει μήκος τουλάχιστον 1).

3. | Xy | <=p. (Το "αντλημένο" μέρος y πρέπει να εμφανιστεί μέσα στους πρώτους χαρακτήρες p).

* Πώς να το χρησιμοποιήσετε για να αποδείξετε τη μη κανονικότητα:

1.

2. Ας υποθέσουμε ότι το μήκος άντλησης είναι *p *. (Δεν ξέρετε τι είναι * p *, αλλά υποθέτετε ότι υπάρχει).

3. Επιλέξτε μια συμβολοσειρά * s * σε l έτσι ώστε | s |> =*p *. Το κλειδί εδώ είναι να επιλέξετε μια συμβολοσειρά * s * που θα οδηγήσει σε μια αντίφαση αργότερα. Αυτό είναι συχνά το πιο δύσκολο κομμάτι.

4. Εξετάστε όλους τους πιθανούς τρόπους διαίρεσης * s * σε * xyz * έτσι ώστε |> 0 και | xy | <=*p *.

5. Για *κάθε πιθανή διαίρεση, βρείτε μια τιμή *i *έτσι ώστε *xy i z* δεν είναι* στο l. Αυτό έρχεται σε αντίθεση με το λεμμά, το οποίο λέει ότι * για όλους * i, xy i Ο Ζ πρέπει να είναι στο Λ.

6. Δεδομένου ότι βρήκατε μια αντίφαση, η αρχική σας παραδοχή ότι το L είναι κανονικό πρέπει να είναι ψευδές. Επομένως, το L δεν είναι κανονικό.

* Παράδειγμα: Έστω l ={a n B n | n> =0}. Αποδείξτε ότι το L δεν είναι κανονικό.

1.

2. ας * p * είναι το μήκος άντλησης.

3. Επιλέξτε * s * =a p B p Παρατηρήστε ότι | s | =2p> =p.

4. Εξετάστε τις πιθανές διαιρέσεις του * s * σε * xyz * με | y |> 0 και | xy | <=*p *. Από το | xy | <=* p * και * s * Ξεκινά με ^p , * xy * πρέπει να αποτελείται μόνο από 'a's. Επομένως:

* x =a j για μερικά j> =0

* y =a k Για μερικά k> 0 (επειδή | y |> 0)

* z =a p-j-k B p

5. Επιλέξτε i =0. Τότε xy i z =xz =a j ένα p-k-k B p =A p-k B p Δεδομένου ότι k> 0, p - k p-k B p δεν είναι * στο Λ.

6. αντίφαση! Το λεμόνι αντλίας λέει ότι για όλα όσα εγώ, xy i z Πρέπει να είναι στο L. Βρήκαμε μια διαίρεση και μια αξία του i για την οποία δεν είναι.

7. Επομένως, l δεν είναι κανονικό.

Βασικές εκτιμήσεις και βέλτιστες πρακτικές:

* Επιλέξτε τη σωστή μέθοδο: Η καλύτερη μέθοδος εξαρτάται από τη γλώσσα.

* Για απλές γλώσσες, η κατασκευή DFA/NFA ή κανονική έκφραση είναι συχνά η πιο εύκολη.

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

*Για τις γλώσσες που υποψιάζονται να είναι *μη κανονικές *, χρησιμοποιήστε το θεώρημα της άντλησης ή του myhill-nerode.

* Σαφήνεια και αυστηρότητα: Όταν αποδεικνύετε ότι μια γλώσσα είναι τακτική, καθορίστε σαφώς την αυτοματοποιημένη σας/κανονική έκφραση και εξηγήστε γιατί δέχεται * όλες τις * χορδές στη γλώσσα και * μόνο * αυτές τις χορδές. Με άλλα λόγια, αποδεικνύουν και τις δύο κατευθύνσεις της επίπτωσης. Μια αόριστη περιγραφή δεν είναι αρκετή.

* ελαχιστοποίηση: Εάν κατασκευάσετε ένα DFA, είναι χρήσιμο (αλλά δεν απαιτείται) για να το ελαχιστοποιήσετε. Ένα ελαχιστοποιημένο DFA είναι μοναδικό για μια δεδομένη γλώσσα.

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

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