Λεξική ανάλυση. Κανονικές γλώσσες και πεπερασμένα αυτόματα
από τον συνολικό αριθμό των χαρακτήρων του αλφαβήτου των συμβόλων και των σημείων των πράξεων και των αγκύλων στην εγγραφή r .Βάση. Τα αυτόματα για εκφράσεις μήκους 1: και φαίνονται στο παρακάτω σχήμα.
Ρύζι. 5.1.
Σημειώστε ότι καθένα από αυτά τα τρία αυτόματα έχει σύνολο τελικών καταστάσεωναποτελείται από ένα κράτος.
βήμα επαγωγής. Ας υποθέσουμε τώρα ότι για το καθένα κοινή έκφρασημήκος<= k
построен соответствующий
НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное
κοινή έκφραση r μήκους k+1 . Ανάλογα με την τελευταία λειτουργία, μπορεί να έχει μία από τις τρεις μορφές: (r 1 + r 2), (r 1 r 2) ή (r 1) * . Έστω και είναι NFA που αναγνωρίζουν τις γλώσσες L r1 και L r2, αντίστοιχα. Χωρίς απώλεια γενικότητας, θα υποθέσουμε ότι έχουν διαφορετικές καταστάσεις: 
.
Στη συνέχεια, το NFA , το διάγραμμα του οποίου φαίνεται στο Σχ. 5.2, αναγνωρίζει τη γλώσσα.
Ρύζι. 5.2.
Αυτό το μηχάνημα έχει σύνολο κρατών, όπου q 0 είναι μια νέα αρχική κατάσταση, q f είναι μια νέα (μοναδική!) τελική κατάσταση και το πρόγραμμα περιλαμβάνει αυτόματα προγράμματα M 1 και M 2 και τέσσερις νέες εντολές μετάβασης: . Προφανώς, η γλώσσα που αναγνωρίζεται από το NFA M περιλαμβάνει όλες τις λέξεις από L ( M 1 ) και από L ( M 2 ) . Από την άλλη πλευρά, κάθε λέξη παίρνει q 0 έως q f , και μετά το πρώτο βήμα η διαδρομή που τη μεταφέρει περνάει από q 0 1 ή q 0 2 . Εφόσον οι καταστάσεις M 1 και M 2 δεν τέμνονται, τότε στην πρώτη περίπτωση αυτή η διαδρομή μπορεί να φτάσει στο q f μόνο με -μετάβαση από q f 1 και μετά 
. Ομοίως, στη δεύτερη περίπτωση.
Για την έκφραση, το διάγραμμα του NFA που αναγνωρίζει τη γλώσσα L r φαίνεται στο παρακάτω σχήμα.
Ρύζι. 5.3.
Αυτό το μηχάνημα έχει σύνολο κρατών 
, αρχική κατάσταση q 0 = q 0 1 , τελική κατάσταση q f =q f 2 , και το πρόγραμμα περιλαμβάνει αυτόματα προγράμματα M 1 και M 2 και μία νέα εντολή - μετάβαση από την τελική κατάσταση M 1 στην αρχική κατάσταση M 2 , δηλ. . Εδώ είναι επίσης προφανές ότι οποιαδήποτε διαδρομή από q 0 = q 0 1 έως q f = q f 2 διέρχεται από μια -μετάβαση από q f 1 σε q 0 2 . Επομένως, οποιαδήποτε λέξη που επιτρέπεται από το M είναι συνένωση κάποιας λέξης από τη L M1 ) με κάποια λέξη από τη L M2 ) , και οποιαδήποτε συνένωση τέτοιων λέξεων επιτρέπεται. Επομένως, το NFA M αναγνωρίζει τη γλώσσα .
Έστω r = r 1 * . Το διάγραμμα του NFA που αναγνωρίζει τη γλώσσα L r =L r1* = L M1 * φαίνεται στην εικ. 5.3.
Ρύζι. 5.3.
Αυτό το μηχάνημα έχει σύνολο κρατών, όπου q 0 είναι μια νέα αρχική κατάσταση, q f είναι μια νέα (μοναδική!) τελική κατάσταση και το πρόγραμμα περιλαμβάνει το αυτόματο πρόγραμμα M 1 και τέσσερις νέες εντολές μετάβασης: . Προφανώς, . Για μια μη κενή λέξη w, εξ ορισμού της επανάληψης 
για κάποιους k >= 1 η λέξη w μπορεί να χωριστεί σε k υπολέξεις: w=w 1 w 2 ... w k και τέλος. Για κάθε i= 1,... ,k η λέξη w i αντιστοιχίζει q 0 1 έως q f 1 . Τότε για τη λέξη w στο διάγραμμα Μ υπάρχει μονοπάτι
Ως εκ τούτου, . Αντίστροφα, αν κάποια λέξη μεταφράζει το q 0 σε q f , τότε είτε υπάρχει είτε μεταφέρεται από τη διαδρομή q 0 1 με -μετάβαση, τελικά από το q f 1 με -μετάβαση τελειώνει σε q f . Επομένως, μια τέτοια λέξη.
Από τα θεωρήματα 4.2 και 5.1 λαμβάνουμε άμεσα
Συμπέρασμα 5.1. Για κάθε κοινή έκφρασημπορεί κανείς να κατασκευάσει αποτελεσματικά ένα ντετερμινιστικό πεπερασμένο αυτόματο που αναγνωρίζει τη γλώσσα που αντιπροσωπεύεται από αυτή την έκφραση.
Αυτή η δήλωση είναι ένα παράδειγμα θεωρήματα σύνθεσης: σύμφωνα με την περιγραφή της εργασίας (γλώσσα ως κοινή έκφραση) ένα πρόγραμμα (DFA) που το εκτελεί έχει κατασκευαστεί αποτελεσματικά. Το αντίστροφο είναι επίσης αλήθεια - θεώρημα ανάλυσης.
Θεώρημα 5.2. Για κάθε ντετερμινιστικό (ή μη ντετερμινιστικό) πεπερασμένο αυτόματο, μπορεί κανείς να κατασκευάσει κοινή έκφραση, το οποίο αντιπροσωπεύει τη γλώσσα που αναγνωρίζεται από αυτό το αυτόματο.
Η απόδειξη αυτού του θεωρήματος είναι αρκετά τεχνική και ξεφεύγει από το πεδίο της πορείας μας.
Έτσι, μπορούμε να συμπεράνουμε ότι η κλάση των πεπερασμένων αυτόματων γλωσσών συμπίπτει με την κλάση κανονικές γλώσσες. Σε αυτό που ακολουθεί θα το ονομάσουμε απλά κατηγορία γλωσσών αυτόματα.
Το αυτόματο M r που κατασκευάζεται στην απόδειξη του Θεωρήματος 5.1
Βασικοί ορισμοί Οι κανονικές εκφράσεις στο αλφάβητο Σ και τα κανονικά σύνολα που δηλώνουν ορίζονται αναδρομικά ως εξής: 1) μια κανονική έκφραση που δηλώνει ένα κανονικό σύνολο. 2) το e είναι μια κανονική έκφραση που δηλώνει ένα κανονικό σύνολο (e). 3) εάν ένα Σ, τότε το a είναι μια κανονική έκφραση που δηλώνει το κανονικό σύνολο (a). 4) αν τα p και q είναι κανονικές εκφράσεις που δηλώνουν κανονικά σύνολα P και Q, τότε το a) (p+q) είναι μια κανονική έκφραση που δηλώνει P Q. β) το pq είναι μια κανονική έκφραση που δηλώνει PQ. γ) Το p* είναι μια κανονική έκφραση που δηλώνει P*. 5) τίποτα άλλο δεν είναι κανονική έκφραση.
Βασικοί ορισμοί Προτεραιότητα: * (επανάληψη) – υψηλότερη προτεραιότητα. αληλουχία; + (ένωση). Άρα 0 + 10* = (0 + (1 (0*))). Παραδείγματα: 1. 01 σημαίνει (01); 2. 0* - (0*); 3. (0+1)* - (0, 1)*; 4. (0+1)* 011 - σημαίνει το σύνολο όλων των χορδών που αποτελούνται από 0 και 1 και τελειώνουν στη συμβολοσειρά 011. 5. (a+b) (a+b+0+1)* σημαίνει το σύνολο όλων των χορδών (0, 1, a, b)* που ξεκινούν με a ή b.
Οι κύριοι ορισμοί του Λήμματος: 1) α + β = β + α 2) * = ε 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5 ) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α
Η επικοινωνία του RT και του RM RM είναι γλώσσες που δημιουργούνται από το RT. Για παράδειγμα: x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d). Συνένωση: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (φάλαινα, γάτα) ή από Λήμματα Νο. 5 και Νο. 6 k(u+o)m = φάλαινα + γάτα (φάλαινα, γάτα) . Επανάληψη: x = a, x* X* = (e, a, aaa, …), δηλαδή x* = e + xxx + …
Σχέση RT και RM Επανάληψη συνένωσης και ένωσης: (xy)* = e + xyxyxy + ... (x + y)* = e + (x + y)(x + y) + ... = = e + xx + xy + yx + yy + xxx + … Παράδειγμα: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110, 111…). Η ένωση είναι ανταλλάξιμη: x + y = y + x Η συνένωση δεν είναι: xy ≠ yx
Σχέση μεταξύ RT και PM Παραδείγματα προτεραιότητας: x + yz (x, yz), (x + y)z (xz, yz), x + y* (e, x, y, εεε, εεε, …), (x + y)* (e, x, y, xx, xy, yx, yy, xxx, …), (xy)* (e, xyxy, …), xy* (x, xyy, xyyy, …). Νέα λήμματα: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; και τα λοιπά.
Κανονικά συστήματα εξισώσεων Εξίσωση με κανονικούς συντελεστές X = α. Το X + b έχει λύση (μικρότερο σταθερό σημείο) a*b: aa*b + b = (aa* + e)b = a*b Σύστημα εξισώσεων με κανονικούς συντελεστές: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 n. Xn X 2 \u003d α 20 + α 21 X 1 + α 22 X 2 + ... + α 2 n. Xn ……………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn. Xn Άγνωστα – Δ = (X 1, X 2, …, Xn).
Κανονικά συστήματα εξισώσεων Αλγόριθμος λύσης (μέθοδος Gauss): Βήμα 1. Ορίστε i = 1. Βήμα 2. Εάν i = n, μεταβείτε στο βήμα 4. Διαφορετικά, γράψτε τις εξισώσεις για το Xi ως Xi = αXi + β (β = β 0 + βi +1 Xi+1 + … + βn.Xn). Στη συνέχεια, στα δεξιά για τις εξισώσεις Xi+1, …, Xn, αντικαθιστούμε το Xi με την κανονική έκφραση α*β. Βήμα 3. Αυξήστε το i κατά 1 και επιστρέψτε στο βήμα 2. Βήμα 4. Γράψτε την εξίσωση για το Xn ως Xn = αXn + β. Πηγαίνετε στο βήμα 5 (με i = n). Βήμα 5. Η εξίσωση για το Xi είναι Xi = αXi + β. Γράψτε στην έξοδο Xi = α*β, στις εξισώσεις για Xi– 1, …, X 1 αντικαθιστώντας το α*β αντί του Xi. Βήμα 6. Εάν i = 1, σταματήστε, διαφορετικά μειώστε το i κατά 1 και επιστρέψτε στο βήμα 5.
Μετατροπή DFA σε RW Για DFA M = (Q, Σ, δ, q 0, F) συνθέτουμε ένα σύστημα με κανονικούς συντελεστές όπου Δ = Q: 1. θέτουμε αij: = ; 2. αν δ(Xi, a) = Xj, a Σ, τότε αij: = αij + a; 3. αν Xi F ή δ(Xi,) = HALT, τότε αi 0: = e. Μετά την επίλυση του επιθυμητού RV θα είναι X 1 = q 0.
Μετατροπή DFA σε RW Παράδειγμα: για έναν αριθμό σταθερού σημείου, παίρνουμε το σύστημα q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 Εδώ: s είναι το πρόσημο του αριθμού, s = "+" + "-"; p – υποδιαστολή, p = ". "; d - αριθμοί, d = "0" + "1" + ... + "9".
Μετατροπή DFA σε RW Λύση: q 0 = *(sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3, q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4, q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e, q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. Από την τρίτη εξίσωση: q 3 \u003d dq 3 + pq 4 + e \u003d d * (pq 4 + e). Από την τέταρτη εξίσωση: q 4 = dq 4 + e = d*.
Μετατροπή DFA σε RW Αντίστροφη: q 3 = d*(pq 4 + e) = d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd* + dd *(pd* + e), q 0 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Έτσι, αυτό το DFA αντιστοιχεί στο RE s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Για απλοποίηση: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) = = spdd* + sdd*(pd* + e) + pdd* + dd*(pd* + e) = (s + e)(pdd* + dd*(pd* + e)) Για συντομότερο συμβολισμό, μπορείτε να χρησιμοποιήσετε θετική επανάληψη aa* = a*a = a+: (s + e )(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)
Μετασχηματισμός DFA σε RT Αντιστοίχιση του γραφήματος της συνάρτησης μετάβασης DFA σε βασικές πράξεις κανονικής έκφρασης: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*
Μετατροπή DFA σε RT Πιο πολύπλοκοι συνδυασμοί πράξεων: q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a a (ab)+ q 2 b q 1 c e + (a + b)c*
Μετατροπή DFA σε RW Για RW (s + e)(pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d
Κανονικές εκφράσεις προγραμματισμού σε πραγματικό χρόνο: Ενσωματωμένο σε πολλές γλώσσες προγραμματισμού (PHP, Java. Script, ...); Υλοποιείται ως πρόσθετα (για παράδειγμα, η κλάση Regex για την πλατφόρμα .NET). Διαφορές στις μορφές γραφής: x; = x + e x(1, 3) = x + xxx κ.λπ.
Προγραμματισμός RT Κατασκευές κλάσης Regex (System.Text.Regular.Expressions): Ερμηνεία ακολουθίας διαφυγής χαρακτήρων b Όταν χρησιμοποιείται σε αγκύλες, ταιριάζει με τον χαρακτήρα "←" (u 0008) t, r, n, a, f, v Tab (u 0009), επιστροφή μεταφοράς (u 000 D), νέα γραμμή (u 000 A), κ.λπ. γ. X Χαρακτήρας ελέγχου (για παράδειγμα, c. C είναι Ctrl+C, u 0003) e Escape (u 001 B) ooo Οκταδικός χαρακτήρας ASCII xhh Δεκαεξαδικός χαρακτήρας ASCII uhhhh Χαρακτήρας Unicode Ο παρακάτω χαρακτήρας δεν είναι ειδικός χαρακτήρας PB. Όλοι οι ειδικοί χαρακτήρες πρέπει να διαφεύγουν με αυτόν τον χαρακτήρα. Παράδειγμα (στο παράδειγμα, δίνεται το μοτίβο και η συμβολοσειρά αναζήτησης, οι αντιστοιχίες που βρέθηκαν στη συμβολοσειρά είναι υπογραμμισμένες): @"rnw+" – "rn. Υπάρχουν n δύο συμβολοσειρές εδώ" .
Προγραμματισμός RT Υποσύνολα χαρακτήρων. Οποιοσδήποτε χαρακτήρας εκτός από το τέλος της συμβολοσειράς (n) Οποιοσδήποτε χαρακτήρας από το σύνολο [^xxx] Οποιοσδήποτε χαρακτήρας εκτός από χαρακτήρες από το σύνολο Οποιοσδήποτε χαρακτήρας από το εύρος ] Αφαιρέστε ένα σύνολο ή εύρος από ένα άλλο p(όνομα) Κάθε χαρακτήρας που καθορίζεται από το Unicode όνομα κατηγορίας P (όνομα) Οποιοσδήποτε χαρακτήρας εκτός από αυτούς που καθορίζονται από την κατηγορία Unicode με όνομα w Σύνολο χαρακτήρων που χρησιμοποιούνται για τον καθορισμό αναγνωριστικών W Σύνολο χαρακτήρων που δεν χρησιμοποιούνται για τον καθορισμό αναγνωριστικών s Διαστήματα S Οτιδήποτε εκτός από κενά d Ψηφία D Όχι ψηφία Παραδείγματα: @ ". +" – "rn. Υπάρχουν n δύο γραμμές εδώ"; @"+" - "0xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" - "0xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0xabcfx"; @"p(Lu)" - "City Lights"; // Lu - κεφαλαία γράμματα @"P(Lu)" - "Πόλη"; @"p(Is. Cyrillic)" - "ha. OS"; // Είναι. Κυριλλικά - Ρωσικά γράμματα
PB Programming Anchor ^, A Στην αρχή της συμβολοσειράς $, Z Στο τέλος της συμβολοσειράς ή μέχρι τον χαρακτήρα "n" στο τέλος της συμβολοσειράς z Στο τέλος της συμβολοσειράς G Όπου τελείωσε η προηγούμενη αντιστοίχιση β Λέξη όριο Β Οποιαδήποτε θέση που δεν βρίσκεται σε όριο λέξης Παραδείγματα: @ "G(d)" - "(1)(3)(5)(9)"; // τρεις αγώνες (1), (2) και (3) @"bnS*ionb" – "δωρεά έθνους"; @"Bendw*b" – "end sends endure lender".
Προγραμματισμός Λειτουργιών RT (ποσοτικοί δείκτες) *, *? Επανάληψη +, +; Θετική επανάληψη; , ? ? Μηδέν ή ένα ταίριασμα (n), (n); Ακριβώς n ταιριάζει (n, ), (n, ); Τουλάχιστον n ταιριάζουν (n, m), (n, m); Από n έως m ταιριάζει Παραδείγματα (οι πρώτοι ποσοτικοί δείκτες είναι άπληστοι, αναζητούν όσο το δυνατόν περισσότερα στοιχεία, οι δεύτεροι είναι τεμπέληδες, αναζητούν όσο το δυνατόν λιγότερα στοιχεία): @"d(3, )" – "888 -5555"; @"^d(3)" - "913 -913"; @"-d(3)$" - "913 -913"; @"5+; 5" - "888 -5555"; // τρεις αγώνες - 55, 55 και 55 @"5+5" - "888 -5555".
Ομαδοποίηση προγραμματισμού RT () Η ομάδα εκχωρεί αυτόματα έναν αριθμό (?:) Να μην αποθηκεύεται η ομάδα (?) ή (? "όνομα") Εάν βρεθεί μια αντιστοίχιση, δημιουργήστε μια ομάδα με όνομα (?) ή Διαγράψτε μια προκαθορισμένη ομάδα και (? "όνομα-όνομα") αποθηκεύστε στη νέα ομάδα μια δευτερεύουσα συμβολοσειρά μεταξύ της προηγουμένως καθορισμένης ομάδας και της νέας ομάδας (? imnsx:) Ενεργοποιεί ή απενεργοποιεί οποιαδήποτε από τις πέντε (? -imnsx:) πιθανές επιλογές στην ομάδα: i - case αναίσθητος; s είναι μία γραμμή (τότε ". " είναι οποιοσδήποτε χαρακτήρας). m – λειτουργία πολλαπλών γραμμών (“^” , “$” – αρχή και τέλος κάθε γραμμής). n - μην καταγράφετε ομάδες χωρίς όνομα. x - εξαιρέστε τα κενά χωρίς διαφυγή από το μοτίβο και συμπεριλάβετε σχόλια μετά το αριθμητικό σύμβολο (#) (?=) Θετική προοπτική μηδενικού μήκους
Προγραμματισμός RE (? !) Μηδενικού μήκους αρνητική επιβεβαίωση προσδοκίας (?) Μη επιστρεφόμενο (άπληστο) μέρος της έκφρασης Παραδείγματα: @"(an)+" – "bananas annals"; @"an+" – "bananas annals"; // σύγκριση, τρεις αντιστοιχίες - an, an και ann @"(? i: an)+" - "ba. NAnas annals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?
Src="https://website/presentation/-112203859_437213351/image-24.jpg" alt="Programming RT Αριθμός αναφοράς Αναφορά ομάδας k Αναφορά ομάδας με όνομα Παραδείγματα: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}
Αντικαταστάσεις προγραμματισμού RT $number Αντικαθιστά το τμήμα της συμβολοσειράς που αντιστοιχεί στην ομάδα με τον καθορισμένο αριθμό $(όνομα) Αντικαθιστά το τμήμα της συμβολοσειράς που αντιστοιχεί στην ομάδα με το καθορισμένο όνομα $$ Αντικαθιστά $ $& Αντικατάσταση με ένα αντίγραφο του πλήρους αντιστοίχιση $` Αντικατάσταση του κειμένου της συμβολοσειράς εισαγωγής μέχρι την αντιστοίχιση $" Αντικατάσταση του κειμένου της γραμμής εισαγωγής μετά την αντιστοίχιση $+ Αντικατάσταση της τελευταίας ομάδας που καταγράφηκε $_ Αντικατάσταση ολόκληρης γραμμής Σχόλια (? #) Ενσωματωμένο σχόλιο # Σχόλιο στο τέλος της γραμμής
Αποτελέσματα προγραμματισμού RT του Regex: Ταίριασμα Regex Maches(). Συλλογή Αντιστοίχιση Ομάδων() Ομάδα. Collection Group Captures() Capture. Collection Captures()
Παράδειγμα προγραμματισμού RT σε C++ CLI (Εφαρμογή Visual C++/CLR/CLR Console): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Match ^m = r-> Match (L"123 456"); int match. Count = 0; while (m->Success) ( Κονσόλα: : Write. Line(L"Match(0)", ++match. Count); for (int i = 1; i Ομάδες->Αριθμός; i++) ( Ομάδα ^g = m->Ομάδες[i]; Κονσόλα: : Γράψτε. Γραμμή(L" Ομάδα (0) = "(1)"", i, g-> Τιμή ); for (int j = 0; j Captures->Count; j++) ( Capture ^c = g->Captures[j]; Console: : Write.Line(L" Capture(0) = "(1)" , θέση = (2), μήκος = (3)", j, c, c->Δείκτης, c->Μήκος); ) ) m = m->Επόμενο. Ταίριασμα(); ) επιστροφή 0; ) Σύστημα: : Κείμενο : : Κανονικό. εκφράσεις
Συμπερίληψη ενεργειών και αναζήτηση σφαλμάτων Περιορισμός του αριθμού των σημαντικών ψηφίων σε έναν αριθμό: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = ds + e = s; = (+|-); pd* + e = (pd*); =(.d*); @"(+|-)? (. d+|d+(. d*)?)" ή @"^(+|-)? (. d+|d+(. d*)?)$" Regex r = νέο Regex (@"^(+|-)? (. (? "ψηφίο"d)+|(? "ψηφίο"δ)+(. (? "ψηφίο"δ)*)?)$"); Ταίριασμα m = r. Ταίριασμα("+1. 23456789"); αν (μ. Επιτυχία) ( Ομάδα g = m. Ομάδες["ψηφίο"]; εάν (ζ. Λήψεις. Αρίθμηση
Ενεργοποίηση ενεργειών και εύρεση σφαλμάτων Προσδιορισμός της θέσης ενός σφάλματος: Regex r = new Regex(@"(+|-)? (. (? "ψηφίο"d)+|(? "ψηφίο"d)+(. (? " ψηφίο"d )*)?)"); string str = "+1.2345!678"; Ταίριασμα m = r. Ταίριασμα(str); if (m. Success) ( Ομάδα g = m. Ομάδες["ψηφίο"]; if (g. Λήψεις. Μέτρηση 0) Κονσόλα. Εγγραφή. Γραμμή("Σφάλμα στη θέση 1: απροσδόκητος χαρακτήρας "(0)"", str ), αλλιώς εάν (m.Length
Ενεργοποίηση ενεργειών και αναζήτηση σφαλμάτων Προσδιορισμός της θέσης του σφάλματος: 1. η πρώτη θέση της συμβολοσειράς εισόδου (1), εάν η πρώτη αντιστοίχιση δεν ξεκινά από τη θέση Ευρετήριο = 0; 2. τη θέση μετά την τελευταία αντιστοίχιση (ταιριάζουν. Μήκος + 1), εάν δεν ταιριάζει με την τελευταία θέση της συμβολοσειράς εισόδου. 3. τη θέση του πρώτου διαλείμματος μεταξύ των αγώνων (αντιστοιχία[i]. Ευρετήριο + αντιστοιχία[i]. Μήκος + 1), εάν ο χαρακτήρας που ακολουθεί τον προηγούμενο αγώνα δεν είναι ο πρώτος χαρακτήρας του επόμενου αγώνα.
ευρετήριο) διάλειμμα? δείκτης = m[i]. Ευρετήριο + m[i]. μήκος; ) Κονσόλα. γράφω. Line("Σφάλμα στη θέση (0) "(1)"", ευρετήριο + 1, str); ) «αβγ. xyz. pqr" είναι σωστό. + abc. xyz. pqr" - σφάλμα στη θέση 1 ("+"). "αλφάβητο. xyz. pqr!" – σφάλμα στη θέση 12 (“!”); "αλφάβητο. xyz!. pqr" - σφάλμα στη θέση 8 ("!").
Συμπερίληψη ενεργειών και αναζήτηση σφαλμάτων Αλλά! "αλφάβητο. xyz. +pqr" - σφάλμα στη θέση 8 (." "). Νέα παραλλαγή μοτίβου: @"w+(. w+)*(. (? !$)); " Επικύρωση: "abc. xyz. +pqr" - σφάλμα στη θέση 9 ("+"); "αλφάβητο. xyz. pqr. "- ένα σφάλμα στη θέση 12 (". ").
Ισορροπημένοι ορισμοί: "(? "x")" προσθέτει ένα στοιχείο στη συλλογή με το όνομα "x"; Το "(? "-x")" αφαιρεί ένα στοιχείο από τη συλλογή "x"; Το "(? (x)(? !))" ελέγχει ότι δεν έχουν απομείνει στοιχεία στη συλλογή "x". Γλώσσα L, που περιγράφει τις ένθετες δηλώσεις της γλώσσας Pascal «αρχίζει τέλος. ': @"^s*((? "αρχίζει+)+(? "-αρχή"τελειώνει*; s*)+)*(? (αρχή)(? !))$".
Είναι πιο βολικό να περιγράψουμε το λεξιλόγιο μιας γλώσσας με τη μορφή κανονικών εκφράσεων και να αναγνωρίσουμε μια γλώσσα με τη βοήθεια του ΚΑ. Επομένως, είναι σημαντικό να μπορούμε να μετατρέπουμε ορισμούς γλώσσας με τη μορφή κανονικών εκφράσεων σε ορισμό με τη μορφή FA. Μια τέτοια μεταμόρφωση πρότεινε ο Kennet Thompson.
Η μηχανή κατάστασης είναι πέντε (S, S, d, S 0, F)
Το S είναι ένα πεπερασμένο σύνολο καταστάσεων.
Το S είναι ένα πεπερασμένο σύνολο έγκυρων σημάτων εισόδου.
d - συνάρτηση μετάβασης. Αντανακλά το σύνολο Sx(SÈ(e)) στο σύνολο των καταστάσεων ενός μη ντετερμινιστικού πεπερασμένου αυτόματου. Για ένα ντετερμινιστικό αυτόματο, η συνάρτηση μετάβασης αντανακλά το σύνολο SxS στο σύνολο καταστάσεων του αυτόματου. Με άλλα λόγια, ανάλογα με την κατάσταση και το σύμβολο εισόδου, το d καθορίζει τη νέα κατάσταση του αυτόματου.
S 0 - αρχική κατάσταση του πεπερασμένου αυτόματου, S 0 О S.
F είναι το σύνολο των τελικών καταστάσεων του αυτόματου, F О S.
Η λειτουργία μιας μηχανής κατάστασης είναι μια ακολουθία βημάτων. Το βήμα καθορίζεται από την κατάσταση του αυτόματου και το σύμβολο εισόδου. Το ίδιο το βήμα συνίσταται στην αλλαγή της κατάστασης του αυτόματου και στην ανάγνωση του επόμενου συμβόλου της ακολουθίας εισόδου.
Υπάρχουν οι ακόλουθοι κανόνες για τη μετατροπή τυπικών εκφράσεων σε μηχανή κατάστασης.
1 Η κανονική έκφραση "e" μετατρέπεται σε ένα αυτόματο δύο καταστάσεων και σε μια e-μετάβαση μεταξύ τους (Εικόνα 1).
Εικόνα 1. - Αυτόματο για ηλεκτρονική μετάβαση
2 Μια κανονική έκφραση από έναν χαρακτήρα "a" μετατρέπεται σε μια μηχανή πεπερασμένης κατάστασης από δύο καταστάσεις και σε μια μετάβαση μεταξύ τους σύμφωνα με το σήμα εισόδου a (Εικόνα 2).
Εικόνα 2. - Αυτόματο για άλματα με σύμβολο α
3 Έστω μια κανονική έκφραση rs και πεπερασμένα αυτόματα για την παράσταση r και η παράσταση s έχουν ήδη δημιουργηθεί. Στη συνέχεια, τα δύο αυτόματα συνδέονται σε σειρά. Το σχήμα 3 δείχνει τα αρχικά αυτόματα για τις γλώσσες r και s. Το σχήμα δείχνει ένα αυτόματο για την αναγνώριση της συνάφειας αυτών των γλωσσών.
Αυτόματο για r Αυτόματο για s
Εικόνα 3. - Αρχικά αυτόματα
Εικόνα 4. - Μηχάνημα για τη σύνδεση γλωσσών
4 Έστω μια κανονική έκφραση r | s και πεπερασμένα αυτόματα έχουν ήδη κατασκευαστεί για την έκφραση r και την παράσταση s (Εικόνα 3). Στη συνέχεια, στο προκύπτον αυτόματο πρέπει να υπάρχει μια εναλλακτική λύση για την εκτέλεση ενός από τα δύο αυτόματα. Δηλαδή το αυτόματο για την έκφραση r | Το s για τα αυτόματα για το r και το s από το Σχήμα 3 έχει τη μορφή που φαίνεται στο Σχήμα 5.
Εικόνα 5. - Μηχάνημα για το συνδυασμό γλωσσών
5 Έστω μια κανονική έκφραση r* με το κατασκευασμένο πεπερασμένο αυτόματο r. Σε αυτή την περίπτωση, εισάγονται δύο νέες καταστάσεις για τη δυνατότητα παράκαμψης του αυτόματου της έκφρασης r και εισάγεται μια e-μετάβαση μεταξύ της τελικής και αρχικής κατάστασης για τη δυνατότητα πολλαπλής επανάληψης του αυτόματου r. Εάν ένα αυτόματο παρόμοιο με το Σχήμα 3 έχει κατασκευαστεί για την κανονική έκφραση r, τότε το πεπερασμένο αυτόματο που φαίνεται στο Σχήμα 6 αντιστοιχεί στην κανονική έκφραση r*.
Ρυθμίσεις
Σύμφωνα με το θεώρημα του Kleene, οποιαδήποτε κανονική έκφραση μπορεί να συσχετιστεί με ένα πεπερασμένο αυτόματο, το οποίο είναι ένα επίσημο μοντέλο του αλγορίθμου για την αναγνώριση λεξημάτων που υποδηλώνονται με αυτήν την κανονική έκφραση. Με τους πιο γενικούς όρους, ένας πεπερασμένος αυτόματος-αναγνωριστής ορίζεται από ένα πεπερασμένο σύνολο καταστάσεων ροής εισόδου χαρακτηριστικές του και μεταβάσεις μεταξύ τους. Μια αλλαγή κατάστασης συμβαίνει όταν λαμβάνετε χαρακτήρες της ροής εισόδου από ένα δεδομένο αλφάβητο σύμφωνα με τη συνάρτηση μετάβασης , η οποία καθορίζει τις πιθανές επόμενες καταστάσεις από τον χαρακτήρα εισόδου και την τρέχουσα κατάσταση. Μεταξύ των πιθανών καταστάσεων, ξεχωρίζονται οι αρχικές (αρχικές) και τελικές (επιτρεπόμενες) καταστάσεις, στις οποίες ο μηχανισμός αναγνώρισης καταστάσεων μπορεί να βρίσκεται, αντίστοιχα, στην αρχή και στην ολοκλήρωση της επεξεργασίας των διακριτικών ροής εισόδου. Εάν η ακολουθία εισόδου χαρακτήρων μπορεί να δημιουργήσει μια ακολουθία μεταβάσεων που μπορεί να μεταφέρει το πεπερασμένο αυτόματο από την αρχική κατάσταση σε ένα από τα τελικά, τότε θεωρείται ότι δέχεται και ανήκει στο κανονικό σύνολο που αναγνωρίζει.
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
Τραπέζι 1
| 0 | 1 | |
| Q1 | Q4 | Ε2 |
| Ε2 | Ε3 | Q1 |
| Ε3 | Ε2 | Q4 |
| Q4 | Q1 | Ε3 |
Οι στήλες του πίνακα μετάβασης αντιπροσωπεύουν τους χαρακτήρες του αλφαβήτου εισόδου και οι σειρές αντιστοιχούν στις τρέχουσες καταστάσεις του DFA. Τα στοιχεία κάθε γραμμής υποδεικνύουν τις καταστάσεις του DFA στις οποίες θα πρέπει να μεταβεί από την τρέχουσα κατάσταση όταν λαμβάνει τους αντίστοιχους χαρακτήρες του αλφαβήτου εισόδου. Συγκεκριμένα, από την πρώτη γραμμή αυτού του πίνακα μετάβασης προκύπτει ότι η λήψη των συμβόλων 0 και 1 στην αρχική κατάσταση Q1 μεταφέρει το DFA στις καταστάσεις Q4 και Q2, αντίστοιχα.
Κατά την αναγνώριση της ακολουθίας εισόδου από τον πίνακα μετάβασης, είναι εύκολο να ανιχνευθούν οι αλλαγές κατάστασης του DFA προκειμένου να προσδιοριστεί εάν επιτυγχάνεται ή όχι μία από τις καταστάσεις αποδοχής. Συγκεκριμένα, για ένα δυαδικό διάνυσμα 01001000 με ζυγό αριθμό μηδενικών και μονάδων, το εξεταζόμενο DFA δημιουργεί την ακόλουθη ακολουθία μεταβάσεων, όπου κάθε μετάβαση επισημαίνεται με τον χαρακτήρα του αλφαβήτου εισόδου που την καλεί:
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
Αυτή η ακολουθία μεταβάσεων τελειώνει με την κατάσταση αποδοχής Q1, επομένως, το δυαδικό διάνυσμα 01001000 ανήκει στο κανονικό σύνολο που αναγνωρίζεται από το εξεταζόμενο DFA και ικανοποιεί την παραπάνω κανονική έκφραση.
Συμπερασματικά, θα πρέπει να σημειωθεί ότι η θεωρούμενη άτυπη μέθοδος κατασκευής
Για περαιτέρω μελέτη των ιδιοτήτων των πεπερασμένων αυτόματων και, ειδικότερα, για την επίλυση του προβλήματος της σύνθεσης, είναι σημαντικό το ακόλουθο θεώρημα.
Θεώρημα 7.7 (θεώρημα προσδιορισμού). Για οποιοδήποτε πεπερασμένο αυτόματο, μπορεί να κατασκευαστεί ένα ισοδύναμο ντετερμινιστικό πεπερασμένο αυτόματο.
Προκειμένου να αποδειχθεί το θεώρημα, είναι απαραίτητο, πρώτα, να περιγραφεί ο αλγόριθμος για την κατασκευή ενός ντετερμινιστικού πεπερασμένου αυτοκινήτου από το αρχικό. Δεύτερον, δικαιολογήστε αυτόν τον αλγόριθμο αποδεικνύοντας αυστηρά ότι πράγματι δίνει ένα πεπερασμένο αυτόματο που είναι ντετερμινιστικό και ισοδύναμο με το αρχικό. Εδώ παρουσιάζουμε μόνο τον αλγόριθμο για την κατασκευή ενός ντετερμινιστικού αυτόματου.
Ο μετασχηματισμός ενός αυθαίρετου πεπερασμένου αυτόματου σε ένα ισοδύναμο ντετερμινιστικό πραγματοποιείται σε δύο στάδια: πρώτα αφαιρούνται τα τόξα με την ετικέτα \λάμδα και μετά πραγματοποιείται ο πραγματικός προσδιορισμός.
1. Αφαίρεση λ-μεταβάσεων (τόξα με ετικέτα \lambda ).
Για να μετακινηθείτε από την αρχική μηχανή κατάστασης M=(V,Q,q_0,F,\δέλτα)στο ισοδύναμο πεπερασμένο αυτόματο M"=(V,Q",q_0,F",\δέλτα")χωρίς μεταβάσεις λ, αρκεί να πραγματοποιηθούν οι ακόλουθοι μετασχηματισμοί στο αρχικό γράφημα M.
ΕΝΑ. Όλες οι καταστάσεις, εκτός από την αρχική κατάσταση, που εισάγονται μόνο με τόξα με την ένδειξη \lambda, καταργούνται. αυτό ορίζει το σύνολο Q" του πεπερασμένου αυτόματου M" . Είναι σαφές ότι Q"\subseteq Q . Σε αυτή την περίπτωση, υποθέτουμε ότι η αρχική κατάσταση παραμένει η ίδια.
σι. Το σύνολο τόξων του πεπερασμένου αυτόματου M" και των ετικετών τους (άρα η συνάρτηση μετάβασης M" ) ορίζεται ως εξής: για οποιεσδήποτε δύο καταστάσεις p,r\in Q",~ p\to_(a)rισχύει εάν και μόνο εάν a\in V , και ένα από τα ακόλουθα ισχύει στο γράφημα M: είτε υπάρχει ένα τόξο από το p έως το r του οποίου η ετικέτα περιέχει το σύμβολο a , είτε υπάρχει μια κατάσταση q τέτοια που p\Rightarrow_(\lambda)^(+)qκαι q\to_(a)r . Σε αυτήν την περίπτωση, η κορυφή q, μιλώντας γενικά, μπορεί να μην ανήκει στο σύνολο Q ", δηλ. να εξαφανιστεί κατά το πέρασμα στο αυτόματο M" (Εικ. 7.11). Αλλά αν q\in Q" , τότε, φυσικά, το τόξο (q,r) θα διατηρηθεί στο M" και το σύμβολο a θα είναι ένα από τα σύμβολα που ανήκουν στην ετικέτα αυτού του τόξου (Εικ. 7.12).
Έτσι, στο M" αποθηκεύονται όλα τα τόξα M των οποίων οι ετικέτες είναι διαφορετικές από το \lambda και που συνδέουν ένα ζεύγος (κορυφές) καταστάσεων από το σύνολο Q" (δεν αφαιρούνται σύμφωνα με το στοιχείο α). Επιπλέον, για οποιαδήποτε τριάδα καταστάσεων p,q,r (όχι απαραίτητα διακριτές!), έτσι ώστε p,r\in Q" και υπάρχει μια διαδρομή μη μηδενικού μήκους από το p στο q του οποίου η ετικέτα είναι ίση με \λάμδα (δηλαδή, η διαδρομή με λ-μεταβάσεις), και από το q στο r οδηγεί ένα τόξο, η ετικέτα του οποίου περιέχει το σύμβολο a του αλφαβήτου εισόδου, στο M" κατασκευάζεται ένα τόξο από το p στο r, η ετικέτα του οποίου περιέχει το σύμβολο a (βλ. Εικ. 7.11).
V. Το σύνολο των τελικών καταστάσεων F" του πεπερασμένου αυτόματου M" περιέχει όλες τις καταστάσεις q\in Q" , δηλαδή τις καταστάσεις του πεπερασμένου αυτόματου M που δεν διαγράφονται σύμφωνα με το στοιχείο α, για τις οποίες q\Rightarrow_(\lambda)^(\ast)q_fγια μερικά q_f\in F (δηλαδή, είτε η ίδια η κατάσταση q είναι η τελική κατάσταση του πεπερασμένου αυτόματου M , είτε από αυτήν υπάρχει μια διαδρομή μη μηδενικού μήκους κατά μήκος των τόξων με την ένδειξη \λάμδα σε μια από τις τελικές καταστάσεις του πεπερασμένου αυτόματο Μ ) (Εικ. 7.13).
2. Πραγματικά αποφασιστικότητα.
Αφήνω M=(Q,V,q_0,F,\δέλτα)είναι ένα πεπερασμένο αυτόματο χωρίς λ-μεταπτώσεις. Ας κατασκευάσουμε ένα ισοδύναμο ντετερμινιστικό πεπερασμένο αυτόματο M_1 .
Αυτό το πεπερασμένο αυτόματο ορίζεται με τέτοιο τρόπο ώστε το σύνολο καταστάσεων του να είναι το σύνολο όλων των υποσυνόλων του συνόλου καταστάσεων του πεπερασμένου αυτόματου M . Αυτό σημαίνει ότι κάθε μεμονωμένη κατάσταση του πεπερασμένου αυτόματου M_1 ορίζεται ως κάποιο υποσύνολο του συνόλου των καταστάσεων του πεπερασμένου αυτόματου M . Σε αυτή την περίπτωση, η αρχική κατάσταση του νέου πεπερασμένου αυτόματου (δηλαδή M_1 ) είναι ένα υποσύνολο μονής γραμμής που περιέχει την αρχική κατάσταση του παλιού πεπερασμένου αυτόματου (δηλαδή M ), και οι τελικές καταστάσεις του νέου πεπερασμένου αυτόματου είναι όλα τέτοια υποσύνολα Q που περιέχουν τουλάχιστον ένα τελικό η κορυφή του αρχικού πεπερασμένου αυτόματου M .
Στο εξής, επιτρέποντας κάποια ελευθερία λόγου, μερικές φορές θα ονομάζουμε καταστάσεις των πεπερασμένων αυτόματων M_1 καταστάσεις-σύνολα. Είναι σημαντικό, ωστόσο, να κατανοήσουμε ξεκάθαρα ότι κάθε τέτοιο σύνολο καταστάσεων είναι μια ξεχωριστή κατάσταση του νέου πεπερασμένου αυτόματου, αλλά όχι ένα σύνολο των καταστάσεων του. Ταυτόχρονα, για το αρχικό («παλιό») πεπερασμένο αυτόματο M, αυτό είναι ακριβώς το σύνολο των καταστάσεων του. Μεταφορικά μιλώντας, κάθε υποσύνολο καταστάσεων του παλιού πεπερασμένου αυτόματου «συμπίπτει» σε μια κατάσταση του νέου πεπερασμένου αυτομάτου*.
*Τυπικά, το σύνολο Q_1 θα πρέπει να οριστεί ως ένα σύνολο που βρίσκεται σε αντιστοιχία ένα προς ένα με το σύνολο 2^Q, αλλά είναι ακόμα πιο βολικό για εμάς να θεωρήσουμε ότι το Q_1 συμπίπτει με το 2^Q, επειδή το σύνολο των καταστάσεων ενός πεπερασμένου αυτόματου μπορεί να είναι οποιοδήποτε μη κενό πεπερασμένο σύνολο.
Η συνάρτηση μετάβασης του νέου πεπερασμένου αυτόματου ορίζεται έτσι ώστε από το σύνολο καταστάσεων S από το σύμβολο εισόδου a το πεπερασμένο αυτόματο M_1 πηγαίνει στο σύνολο καταστάσεων, το οποίο είναι η ένωση όλων των συνόλων καταστάσεων του παλιού πεπερασμένου αυτόματου, στο το οποίο αυτό το παλιό πεπερασμένο αυτόματο περνάει με το σύμβολο a από κάθε σύνολο κατάστασης S . Έτσι, το πεπερασμένο αυτόματο M_1 είναι ντετερμινιστικό από την κατασκευή.
Η παραπάνω λεκτική περιγραφή μπορεί να μεταφραστεί σε τύπους ως εξής: κατασκευάζουμε τη μηχανή κατάστασης M_1 έτσι ώστε
M_1=(Q_1,V,\(q_0\),F_1,\δέλτα_1), Οπου
\begin(cases)Q_1=2^Q,\quad F_1=\(T\colon\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\forall S\subseteq Q) (\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Bigr). \end (περιπτώσεις)
Ας δώσουμε προσοχή στο γεγονός ότι μεταξύ των καταστάσεων του νέου πεπερασμένου αυτόματου υπάρχει μια κατάσταση \varnothing, και, σύμφωνα με το (7.8) \delta_1(\varnothing,a)=\varnothingγια οποιονδήποτε χαρακτήρα εισόδου a . Αυτό σημαίνει ότι, όταν βρεθεί σε μια τέτοια κατάσταση, η μηχανή κατάστασης M_1 δεν θα την αφήσει. Γενικά, οποιαδήποτε κατάσταση q ενός πεπερασμένου αυτόματου έτσι ώστε για οποιοδήποτε σύμβολο εισόδου a έχουμε \δέλτα(q,a)=q ονομάζεται κατάσταση απορρόφησης του πεπερασμένου αυτόματου. Έτσι, η κατάσταση \varnothing της ντετερμινιστικής μηχανής καταστάσεων M_1 απορροφά. Είναι επίσης χρήσιμο να σημειωθεί ότι \delta_1(S,a)=\varnothingεάν και μόνο εάν για κάθε q\in S (καταστάσεις του παλιού πεπερασμένου αυτόματου από το σύνολο των καταστάσεων S ) \delta(q,a)=\varnothing, δηλ. στο γράφημα M, κάθε τέτοια κατάσταση q δεν αφήνει κανένα τόξο σημειωμένο με το σύμβολο a .
Μπορεί να αποδειχθεί ότι το πεπερασμένο αυτόματο που λαμβάνεται από έναν τέτοιο αλγόριθμο είναι ισοδύναμο με τον αρχικό.
Παράδειγμα 7.9.Προσδιορίζουμε το πεπερασμένο αυτόματο που φαίνεται στο Σχ. 7.14.
Ένα ισοδύναμο πεπερασμένο αυτόματο χωρίς λ-μεταβάσεις φαίνεται στο σχήμα. 7.15. Σημειώστε ότι η κορυφή q_2 εξαφανίζεται, αφού μόνο "κενά" τόξα μπαίνουν σε αυτήν.
Για να προσδιορίσετε το αυτόματο που προκύπτει, δεν είναι απολύτως απαραίτητο να γράψετε όλες τις 2^3=8 καταστάσεις του, πολλές από τις οποίες μπορεί να μην είναι προσβάσιμες από την αρχική κατάσταση \(q_0\) . Για να λάβουμε προσβάσιμες από \(q_0\) καταστάσεις, και μόνο από αυτές, χρησιμοποιούμε τη λεγόμενη μέθοδο έλξης.
Αυτή η μέθοδος μπορεί να περιγραφεί στη γενική περίπτωση ως εξής.
Στο αρχικό πεπερασμένο αυτόματο (χωρίς κενά τόξα), ορίζουμε όλα τα σύνολα καταστάσεων που είναι προσβάσιμα από την αρχική, δηλ. για κάθε χαρακτήρα εισόδου a βρίσκουμε το σύνολο \delta(q_0,a) . Κάθε τέτοιο σετ στο νέο αυτόματο είναι μια κατάσταση άμεσα προσβάσιμη από την αρχική.
Για καθένα από τα καθορισμένα σύνολα καταστάσεων S και κάθε σύμβολο εισόδου a, βρίσκουμε το σύνολο \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom(A)^(.))). Όλες οι καταστάσεις που λαμβάνονται σε αυτό το βήμα θα είναι οι καταστάσεις ενός νέου (ντετερμινιστικού) αυτόματου, προσβάσιμο από την αρχική κορυφή κατά μήκος μιας διαδρομής μήκους 2. Επαναλαμβάνουμε την περιγραφόμενη διαδικασία μέχρι να μην εμφανιστούν νέα σύνολα καταστάσεων (συμπεριλαμβανομένου του κενού). Μπορεί να φανεί ότι στην περίπτωση αυτή λαμβάνονται όλες οι καταστάσεις του πεπερασμένου αυτόματου M_1 που είναι προσβάσιμες από την αρχική κατάσταση \(q_0\) .
Για τη μηχανή πεπερασμένης κατάστασης στο Σχ. 7.15 έχουμε:
\begin(aligned)& \delta_1(\(q_0\),a)=\(q_1\);\qquad \delta_1(\(q_0\),b)=\(q_1,q_3\);\\ & \ delta_1(\(q_1\),a)=\(q_1\);\qquad \delta_1(\(q_1\),b)=\(q_1\);\\ & \delta_1(\(q_1,q_3\) ,a)= \delta(q_1,a)\cup \delta(q_3,a)= \(q_1\)\cup\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \δέλτα(q_1,b)\κύπελλο \δέλτα(q_3,b)= \(q_1\)\κύπελλο\(q_1\)=\(q_1\). \end (ευθυγραμμισμένο)
Δεδομένου ότι δεν υπάρχουν άλλα νέα σύνολα καταστάσεων, η διαδικασία "έλξης" τελειώνει εδώ και παίρνουμε το γράφημα που φαίνεται στο Σχ. 7.16.
Συμπλήρωμα κανονικής γλώσσας
Μία από τις σημαντικές θεωρητικές συνέπειες του θεωρήματος του προσδιορισμού είναι το ακόλουθο θεώρημα.
Θεώρημα 7.8. Το συμπλήρωμα μιας κανονικής γλώσσας είναι μια κανονική γλώσσα.
Έστω L μια κανονική γλώσσα στο αλφάβητο V . Τότε το συμπλήρωμα της γλώσσας L (ως σύνολο λέξεων) είναι η γλώσσα \overline(L)=V^(\ast)\setminus L.
Σύμφωνα με το Θεώρημα 7.7, για μια κανονική γλώσσα L, μπορεί να κατασκευαστεί ένα ντετερμινιστικό πεπερασμένο αυτόματο M που δέχεται το L . Δεδομένου ότι σε ένα ντετερμινιστικό αυτόματο από κάθε κορυφή, για κάθε σύμβολο εισόδου, ορίζεται μια μετάβαση σε μία ακριβώς κορυφή, τότε, όποια κι αν είναι η συμβολοσειρά x στο αλφάβητο V , υπάρχει μια μοναδική διαδρομή για αυτήν στο M, που ξεκινά από την αρχική κατάσταση στην οποία διαβάζεται η συμβολοσειρά x. Είναι σαφές ότι η συμβολοσειρά x επιτρέπεται από το αυτόματο M , δηλαδή x\in L(M) , εάν και μόνο εάν η τελευταία κατάσταση της καθορισμένης διαδρομής είναι τελική. Αυτό σημαίνει ότι η αλυσίδα x\notin L(M) εάν και μόνο εάν η τελευταία κατάσταση της καθορισμένης διαδρομής δεν είναι τελική. Αλλά χρειαζόμαστε απλώς ένα πεπερασμένο αυτόματο M", το οποίο επιτρέπει την αλυσίδα x εάν και μόνο εάν το αρχικό πεπερασμένο αυτόματο M δεν το επιτρέπει. Επομένως, μετατρέποντας κάθε τελική κατάσταση του M σε μη τελική και αντίστροφα, παίρνουμε ένα ντετερμινιστικό αυτόματο που επιτρέπει τη συμπλήρωση της γλώσσας L .
Το αποδεδειγμένο θεώρημα μας επιτρέπει να κατασκευάσουμε ένα πεπερασμένο αυτόματο που δεν επιτρέπει ένα συγκεκριμένο σύνολο αλυσίδων με την ακόλουθη μέθοδο: πρώτα, κατασκευάζουμε ένα αυτόματο που επιτρέπει ένα δεδομένο σύνολο αλυσίδων, μετά το προσδιορίζουμε και περνάμε στο αυτόματο για το συμπλήρωμα όπως υποδεικνύεται στην απόδειξη του Θεωρήματος 7.8.
Παράδειγμα 7.10.ΕΝΑ. Ας δημιουργήσουμε ένα πεπερασμένο αυτόματο που επιτρέπει όλες τις συμβολοσειρές στο αλφάβητο \(0;1\) εκτός από τη συμβολοσειρά 101.
Αρχικά, κατασκευάζουμε ένα πεπερασμένο αυτόματο που επιτρέπει μια μονή αλυσίδα 101. Αυτό το αυτόματο φαίνεται στο Σχ. 7.17.
Αυτό το αυτόματο είναι σχεδόν ντετερμινιστικό, αλλά όχι ντετερμινιστικό, αφού δεν έχει οριστεί πλήρως. Ας το προσδιορίσουμε και ας λάβουμε ένα ντετερμινιστικό ισοδύναμο πεπερασμένο αυτόματο που φαίνεται στο Σχ. 7.18.
Και τέλος, περνώντας στην προσθήκη (και μετονομάζοντας τις καταστάσεις), παίρνουμε το αυτόματο που φαίνεται στο Σχ. 7.19.
Σημειώστε ότι στο προκύπτον αυτόματο, όλες οι κορυφές, εκτός από την κορυφή s_3, είναι τελικές.
Σημειώστε επίσης ότι η μετάβαση στο συμπλήρωμα, η οποία συζητείται στην απόδειξη του Θεωρήματος 7.8, μπορεί να πραγματοποιηθεί μόνο σε ένα ντετερμινιστικό αυτόματο. Αν αντιστρέψαμε τους ρόλους των τελικών και μη τελικών κορυφών στο αυτόματο που φαίνεται στο Σχ. 7.17, θα παίρναμε ένα αυτόματο που δέχεται τη γλώσσα \(\λάμδα,1,10\) , η οποία δεν είναι - όπως είναι εύκολο να δει κανείς - το σύνολο όλων των συμβολοσειρών εκτός από τη συμβολοσειρά 101.
Σημειώστε επίσης ότι η μηχανή πεπερασμένης κατάστασης στο Σχ. Το 7.19 επιτρέπει όλες τις συμβολοσειρές που περιέχουν μια εμφάνιση της συμβολοσειράς 101 αλλά δεν ταιριάζουν με την ίδια τη συμβολοσειρά. Εδώ, για παράδειγμα, είναι η διαδρομή που φέρει την αλυσίδα 1011: s_0,s_1,s_2,s_3,t.
σι. Ας κατασκευάσουμε ένα πεπερασμένο αυτόματο που επιτρέπει όλες τις συμβολοσειρές στο αλφάβητο \(0;1\) εκτός από αυτές που περιέχουν μια εμφάνιση της συμβολοσειράς 101. Θεωρήστε μια γλώσσα L , κάθε συμβολοσειρά της οποίας περιέχει μια εμφάνιση της συμβολοσειράς 101. Μπορεί να είναι ορίζεται ως εξής:
L=(0+1)^(\ast)101(0+1)^(\ast).
Πρέπει να φτιάξουμε ένα αυτόματο που θα συμπληρώνει τη γλώσσα L.
Απευθείας από την κανονική έκφραση σε αυτή την περίπτωση, είναι εύκολο να κατασκευαστεί ένα πεπερασμένο αυτόματο που επιτρέπει τη γλώσσα L (Εικ. 7.20).
Στη συνέχεια, με τη μέθοδο «τραβήγματος» θα πραγματοποιήσουμε τον προσδιορισμό. Το αποτέλεσμα του προσδιορισμού φαίνεται στο σχ. 7.21.
Για πλήρη επίλυση του προβλήματος, μόνο η Εικ. 7.21 ανταλλάξτε τους ρόλους της τελικής και της μη τελικής κορυφής (Εικ. 7.22).
V. Ας συζητήσουμε την ιδέα της κατασκευής ενός πεπερασμένου αυτόματου που επιτρέπει εκείνες και μόνο εκείνες τις συμβολοσειρές στο αλφάβητο \(0;1\) που δεν ξεκινούν με τη συμβολοσειρά 01 και δεν τελειώνουν με τη συμβολοσειρά 11 (δηλ., συμβολοσειρές του μορφή 01x και οι συμβολοσειρές της μορφής y11 δεν επιτρέπονται, ό,τι κι αν υπήρχαν αλυσίδες x,y\in\(0;1\) ).
Σε αυτήν την περίπτωση, το συμπλήρωμα της γλώσσας για την οποία θέλετε να δημιουργήσετε ένα πεπερασμένο αυτόματο είναι το σύνολο όλων αυτών των συμβολοσειρών μηδενικών και μονάδων που ξεκινούν με τη συμβολοσειρά 01 ή τελειώνουν με τη συμβολοσειρά 11. Ένα αυτόματο που δέχεται αυτό το σύνολο συμβολοσειρών είναι κατασκευασμένο ως αυτόματο για συνδυασμό 01(0+1)^(\ast)+(0+1)^(\ast)11με τον ίδιο τρόπο όπως και στην απόδειξη του θεωρήματος του Kleene (βλ. Θεώρημα 7.6).
Η ιδιότητα της κλάσης των κανονικών γλωσσών που κλείνει κάτω από το συμπλήρωμα (βλ. Θεώρημα 7.8) υποδηλώνει αμέσως ότι αυτή η κλάση είναι κλειστή υπό τομή, τη θεωρία συνόλων και τις συμμετρικές διαφορές.
Συμπέρασμα 7.3. Για οποιεσδήποτε δύο κανονικές γλώσσες L_1 και L_2, ισχύουν οι ακόλουθες δηλώσεις:
1) η τομή L_1\cap L_2 είναι κανονική.
2) η διαφορά L_1\setminus L_2 είναι κανονική.
3) συμμετρική διαφορά L_1\τρίγωνο L_2τακτικός.
Η εγκυρότητα των δηλώσεων προκύπτει από τις ταυτότητες:
\begin(aligned) &(\scriptstyle(\mathsf(1))))\quad L_1\cap L_2= \overline(\overline(L_1) \cup\overline(L_2))\,;\\ &(\scriptstyle (\mathsf(2)))\quad L_1\setminus L_2= L_1\cap \overline(L_2)\,;\\ &(\scriptstyle(\mathsf(3))))\quad L_1\,\triangle\ ,L_2 = (L_1\κύπελλο L_2)\setminus (L_1\cap L_2).\end (ευθυγραμμισμένο)
Πρώτον, τα ληφθέντα αποτελέσματα μας επιτρέπουν να ισχυριστούμε ότι η τάξη των κανονικών γλωσσών σε σχέση με τις πράξεις ένωσης, τομής και πρόσθεσης είναι μια άλγεβρα Boole, στην οποία η μονάδα είναι η καθολική γλώσσα και το μηδέν είναι η κενή γλώσσα. . Δεύτερον, αυτές οι αλγεβρικές ιδιότητες της οικογένειας των κανονικών γλωσσών μας επιτρέπουν να λύσουμε το σημαντικό πρόβλημα της αναγνώρισης της ισοδυναμίας δύο αυθαίρετων πεπερασμένων αυτόματα.
Σύμφωνα με τον ορισμό 7.10, τα πεπερασμένα αυτόματα είναι ισοδύναμα εάν οι γλώσσες που επιτρέπουν είναι οι ίδιες. Επομένως, για να επαληθεύσουμε την ισοδυναμία των αυτόματων M_1 και M_2, αρκεί να αποδειχθεί ότι η συμμετρική διαφορά των γλωσσών L(M_1) και L(M_2) είναι κενή. Για να γίνει αυτό, με τη σειρά του, αρκεί να κατασκευάσουμε ένα αυτόματο που να παραδέχεται αυτή τη διαφορά και να επαληθεύει ότι η γλώσσα που παραδέχεται είναι κενή. Γενικά, το πρόβλημα της αναγνώρισης ότι μια γλώσσα μηχανής κατάστασης είναι κενή ονομάζεται πρόβλημα κενού κατάστασης μηχανής. Για να λυθεί αυτό το πρόβλημα, αρκεί να βρούμε το σύνολο των τελικών καταστάσεων του αυτόματου που είναι προσβάσιμες από την αρχική κατάσταση. Δεδομένου ότι η μηχανή πεπερασμένης κατάστασης είναι ένα κατευθυνόμενο γράφημα, αυτό το πρόβλημα μπορεί να λυθεί, για παράδειγμα, χρησιμοποιώντας την αναζήτηση κατά πλάτος. Η γλώσσα που επιτρέπεται από το πεπερασμένο αυτόματο είναι κενή εάν και μόνο εάν το σύνολο των τελικών καταστάσεων που είναι προσβάσιμες από την αρχική κατάσταση είναι κενό. Στην πράξη, είναι προτιμότερο να αναγνωρίζουμε την ισοδυναμία των πεπερασμένων αυτόματα χρησιμοποιώντας έναν αλγόριθμο ελαχιστοποίησης, αλλά τώρα είναι σημαντικό για εμάς να τονίσουμε ότι η θεμελιώδης δυνατότητα επίλυσης του προβλήματος της ισοδυναμίας προκύπτει από το Θεώρημα 7.7 και τις αλγεβρικές του συνέπειες.
