Κανονική γλώσσα

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

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

Εναλλακτικά, μια κανονική γλώσσα μπορεί να οριστεί ως η γλώσσα εκείνη που αναγνωρίζεται από ένα πεπερασμένο αυτόματο. Η ισοδυναμία των κανονικών εκφράσεων και των αυτομάτων είναι γνωστή ως το θεώρημα του Kleene.[1] Στην ιεραρχία του Chomsky, οι κανονικές γλώσσες ορίζονται ως εκείνες που παράγονται από γραμματικές τύπου 3 (κανονικές γραμματικές).

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

Τυπικός ορισμός[Επεξεργασία | επεξεργασία κώδικα]

Μια ομάδα κανονικών γλωσσών για ένα αλφάβητο Σ ορίζεται αναδρομικά ως εξής:

  • Η κενή γλώσσα Ø και η γλώσσα της κενής συμβολοσειράς {ε} είναι κανονικές γλώσσες.
  • Για κάθε a ∈ Σ (a ανήκει στο Σ), η γλώσσα {a} είναι μια κανονική γλώσσα.
  • Αν οι Α και Β είναι κανονικές γλώσσες, τότε η ένωση A ∪ B, η συνένωση A • B και το άστρο του Kleene A* είναι κανονικές γλώσσες.
  • Καμία άλλη γλώσσα στο Σ δεν είναι κανονική.

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

Παραδείγματα[Επεξεργασία | επεξεργασία κώδικα]

Όλες οι πεπερασμένες γλώσσες είναι κανονικές. Πιο συγκεκριμένα, η γλώσσα της κενής συμβολοσειράς {ε} = Ø* είναι κανονική. Άλλα τυπικά παραδείγματα είναι η γλώσσα που αποτελείται από όλες τις συμβολοσειρές στο αλφάβητο {a, b} που περιέχουν άρτιο πλήθος ab, ή η γλώσσα που αποτελείται από όλες τις συμβολοσειρές της μορφής: πολλαπλά a ακολουθούμενα από πολλαπλά b.

Ένα απλό παράδειγμα γλώσσας που δεν είναι κανονική αποτελεί το σύνολο των συμβολοσειρών { anbn | n ≥ 0 }[2]. Εμπειρικά, η γλώσσα αυτή δεν μπορεί να αναγνωριστεί από ένα πεπερασμένο αυτόματο διότι αυτό έχει πεπερασμένη μνήμη και δεν είναι ικανό να θυμάται το ακριβές πλήθος των a. Σε επόμενη παράγραφο παρουσιάζονται τεχνικές για συστηματική επαλήθευση αυτού του γεγονότος.

Ισοδύναμοι φορμαλισμοί[Επεξεργασία | επεξεργασία κώδικα]

Μια κανονική γλώσσα ικανοποιεί τις παρακάτω ισοδύναμες ιδιότητες:

  1. είναι η γλώσσα μιας κανονικής έκφρασης (σύμφωνα με τον παραπάνω ορισμό)
  2. είναι η γλώσσα που γίνεται αποδεκτή από ένα μη ντετερμινιστικό πεπερασμένο αυτόματο (NFA)
  3. είναι η γλώσσα που γίνεται αποδεκτή από ένα ντετερμινιστικό πεπερασμένο αυτόματο (DFA)
  4. μπορεί να παραχθεί από μια κανονική γραμματική
  5. είναι η γλώσσα που γίνεται αποδεκτή από ένα εναλλασσόμενο πεπερασμένο αυτόματο
  6. μπορεί να παραχθεί από μια γραμματική προθέματος
  7. μπορεί να γίνει αποδεκτή από μια μηχανή Turing που μόνο διαβάζει
  8. μπορεί να οριστεί με monadic λογική δεύτερης τάξης (MSOL)
  9. μπορεί να αναγνωριστεί από ένα πεπερασμένο monoid M, που σημαίνει ότι είναι η αντίστροφη εικόνα (preimage) { w∈Σ* | f(w)∈S } ενός συνόλου S κάποιου πεπερασμένου monoid M υπό τον monoid ομομορφισμό f: Σ* → M από το free monoid στο αλφάβητό του.
  10. το πλήθος των κλάσεων ισοδυναμίας της "συντακτικής σχέσης" του ~ είναι πεπερασμένο (το πλήθος αυτό είναι ίσο με τον αριθμό των καταστάσεων σε ένα ελάχιστο ντετερμινιστικό πεπερασμένο αυτόματο που δέχεται το L).

Οι ιδότητες 9 και 10 αποτελούν αμιγώς αλγεβρικές προσεγγίσεις για τον ορισμό των κανονικών γλωσσών. Ένα παρόμοιο σύνολο προτάσεων μπορεί να σχηματιστεί για ένα monoid M⊂Σ*. Σε αυτή την περίπτωση, η ισοδυναμία πάνω στο Μ οδηγεί στην έννοια μιας αναγνωρίσιμης γλώσσας.

Κάποιοι συγγραφείς χρησιμοποιούν κάποια από τις παραπάνω ιδιότητες, πλην της πρώτης, ως εναλλακτικό ορισμό των κανονικών γλωσσών.

Κάποιες από τις παραπάνω ισοδυναμίες, ιδιαίτερα ανάμεσα στις τέσσερις πρώτες, στη βιβλιογραφία αναφέρονται ως θεώρημα του Kleene. Το ποιο ή ποια ακριβώς υποσύνολα παίρνουν αυτή την ονομασία ποικίλλει ανάμεσα στους διαφορετικούς συγγραφείς. Κάποιο σύγγραμμα ονομάζει την ισοδυναμία ανάμεσα στις κανονικές εκφράσεις και τα NFA (ιδιότητες 1 και 2) ως "θεώρημα του Kleene"[3], ενώ κάποιο άλλο καλεί έτσι την ισοδυναμία ανάμεσα στις κανονικές εκφράσεις και τα DFA (ιδιότητες 1 και 3)[4]. Δύο άλλα εγχειρίδια αποδεικνύουν πρώτα την εκφραστική ισοδυναμία ανάμεσα στα NFA και DFA (ιδιότητες 2 και 3) κι έπειτα ορίζουν ως "θεώρημα του Kleene" την ισοδυναμία ανάμεσα στις κανονικές εκφράσεις και τα πεπερασμένα αυτόματα (τα οποία και λένε πως περιγράφουν "αναγνωρίσιμες γλώσσες")[5][6]. Ένα άλλο κείμενο, γλωσσολογικού προσανατολισμού, αρχικά εξισώνει τις κανονικές γραμματικές (ιδιότητα 4) με τα DFA και NFA, καλεί τις γλώσσες που παράγονται από αυτά "κανονικές", έπειτα εισάγει τις κανονικές εκφράσεις που ορίζει ότι περιγράφουν "λογικές γλώσσες" και τέλος αναφέρεται στο "θεώρημα του Kleene" ως τη σύμπτωση κανονικών και λογικών γλωσσών[7]. Άλλοι συγγραφείς απλώς ορίζουν τη "λογική έκφραση" και τις "κανονικές εκφράσεις" ως συνώνυμα και κάνουν το ίδιο με τις "λογικές γλώσσες" και τις "κανονικές γλώσσες"[8].

Ιδιότητες κλεισίματος (closure)[Επεξεργασία | επεξεργασία κώδικα]

Οι κανονικές γλώσσες κλείνουν υπό τις διάφορες πράξεις, δηλαδή αν οι γλώσσες K και L είναι κανονικές, τότε το αποτέλεσμα των παρακάτω πράξεων αποτελεί επίσης κανονική γλώσσα:

Ιδιότητες αποφασισιμότητας[Επεξεργασία | επεξεργασία κώδικα]

Δοθέντων δύο ντετερμινιστικών πεπερασμένων αυτομάτων Α και Β, μπορεί να αποφασιστεί εάν αποδέχονται την ίδια γλώσσα. Ως επακόλουθο, με χρήση των παραπάνω ιδιοτήτων κλεισίματος, μπορούμε να αποφανθούμε και για τα ακόλουθα προβλήματα, δοθέντων τυχαίων ντετερμινιστικών πεπερασμένων αυτομάτων Α και Β που αποδέχονται τις γλώσσες LA και LB αντίστοιχα:

  • Περιέχεται η μια γλώσσα στην άλλη: LA ⊆ LB ;
  • Είναι οι γλώσσες ασυμβίβαστες: LA ∩ LB = {};
  • Είναι κάποια γλώσσα κενή: LA = {};
  • Είναι κάποια γλώσσα καθολική: LA = Σ*;
  • Ανήκει μια συμβολοσειρά σε κάποια γλώσσα: αν a ∈ Σ*, τότε είναι a ∈ LB;

Για τις κανονικές εκφράσεις, το πρόβλημα της καθολικότητας είναι NP-complete ακόμη και για αλφάβητο με ένα στοιχείο. Για μεγαλύτερα αλφάβητα, το πρόβλημα γίνεται PSPACE-complete[11][12]. Αν οι κανονικές εκφράσεις επεκταθούν ώστε να επιτρέπουν κι έναν τελεστή τετραγώνου, με το "A2" να είναι ισοδύναμο με το "AA", τότε και πάλι μόνο κανονικές γλώσσες μπορούν να περιγραφούν, αλλά το πρόβλημα της καθολικότητας αποκτά ένα εκθετικό χωρικό κάτω φράγμα[13][14][15]

Αποτελέσματα πολυπλοκότητας[Επεξεργασία | επεξεργασία κώδικα]

Στη θεωρία πολυπλοκότητας, η κλάση πολυπλοκότητας όλων των κανονικών γλωσσών αναφέρεται μερικές φορές ως REGULAR ή REG και ισοδυναμεί με DSPACE(O(1)), δηλαδή τα προβλήματα απόφασης που μπορούν να επιλυθούν σε σταθερό χώρο (ο χώρος που χρησιμοποιείται είναι ανεξάρτητος του μεγέθους της εισόδου). Ισχύει ότι REGULAR ≠ AC0, αφού εμπεριέχει το πρόβλημα της ισοτιμίας κατά το οποίο πρέπει να αποφανθούμε αν το πλήθος των 1 ψηφίων στην είσοδο είναι άρτιο ή περιττό, και αυτό το πρόβλημα δεν ανήκει στο AC0.[16] Από την άλλη πλευρά, η REGULAR δεν περιλαμβάνει την AC0, διότι η μη κανονική γλώσσα των παλίνδρομων ή η μη κανονική γλώσσα μπορούν αμφότερες να αναγνωριστούν στην AC0.[17]

Αν μια γλώσσα δεν είναι κανονική, τότε απαιτεί μια μηχανή με τουλάχιστον Ω(log log n) χώρο για την αναγνώριση (όπου n το μέγεθος της εισόδου)[18]. Με άλλα λόγια, το DSPACE(o(log log n)) ισοδυναμεί με την κλάση των κανονικών γλωσσών. Στην πράξη, τα περισσότερα μη κανονικά προβλήματα επιλύονται από μηχανές που καταλαμβάνουν τουλάχιστον λογαριθμικό χώρο.

Θέση στην ιεραρχία του Chomsky[Επεξεργασία | επεξεργασία κώδικα]

Η κανονική γλώσσα στις κλάσεις της ιεραρχίας Chomsky.

Για να εντοπίσουμε τις κανονικές γλώσσες στην ιεραρχία Chomsky, παρατηρούμε αρχικά ότι κάθε κανονική γλώσσα είναι ελεύθερη συμφραζομένων (context-free). Το αντίστροφο δεν ισχύει· για παράδειγμα, η γλώσσα που αποτελείται από όλες τις συμβολοσειρές με ίσο αριθμό a και b είναι γλώσσα χωρίς συμφραζόμενα, αλλά όχι κανονική. Για να αποδείξουμε ότι μια τέτοια γλώσσα δεν είναι κανονική, συχνά χρησιμοποιούμε το θεώρημα Myhill-Nerode ή το pumping lemma ανάμεσα σε άλλες μεθόδους[19].

Κάποιες σημαντικές υπο-κλάσεις των κανονικών γλωσσών είναι:

  • Πεπερασμένες γλώσσες - εκείνες που περιέχουν μόνο ένα πεπερασμένο πλήθος λέξεων[20]. Αυτές είναι κανονικές γλώσσες, αφού μπορούμε να δημιουργήσουμε μια κανονική έκφραση με την ένωση κάθε λέξης στη γλώσσα.
  • Star-free γλώσσες, οι οποίες μπορούν να περιγραφούν από μια κανονική έκφραση που κατασκευάζεται από το κενό σύμβολο, γράμματα, συνένωση και όλους τους Boolean τελεστές περιλαμβανομένου του συμπληρώματος, αλλά όχι του Άστρου του Kleene: αυτή η κλάση περιλαμβάνει όλες τις πεπερασμένες γλώσσες[21].
  • Κυκλικές γλώσσες, που ικανοποιούν τις συνθήκες uv ∈ L ⇔ vu ∈ L και w ∈ L ⇔ w n ∈ L.[22][23]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. ↑ Sheng Yu (1997). «Regular languages». Στο: Grzegorz Rozenberg and Arto Salomaa. Handbook of Formal Languages: Volume 1. Word, Language, Grammar. Springer. σελ. 41. ISBN 978-3-540-60420-4. 
  2. ↑ Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).
  3. ↑ Robert Sedgewick· Kevin Daniel Wayne (2011). Algorithms. Addison-Wesley Professional. σελ. 794. ISBN 978-0-321-57351-3. 
  4. ↑ Jean-Paul Allouche· Jeffrey Shallit (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. σελ. 129. ISBN 978-0-521-82332-6. 
  5. ↑ Mark V. Lawson (2003). Finite Automata. CRC Press. σελίδες 98–103. ISBN 978-1-58488-255-8. 
  6. ↑ Kenneth Rosen (2011). Discrete Mathematics and Its Applications 7th edition. McGraw-Hill Science. σελίδες 873–880. [νεκρός σύνδεσμος]
  7. ↑ Horst Bunke· Alberto Sanfeliu (Ιανουαρίου 1990). Syntactic and Structural Pattern Recognition: Theory and Applications. World Scientific. σελ. 248. ISBN 978-9971-5-0566-0. 
  8. ↑ Ruslan Mitkov (2003). The Oxford Handbook of Computational Linguistics. Oxford University Press. σελ. 754. ISBN 978-0-19-927634-9. 
  9. ↑ Salomaa (1981) p.28
  10. ↑ Salomaa (1981) p.27
  11. ↑ Hunt, H. B., III (1973), «On the time and tape complexity of languages. I», Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), Assoc. Comput. Mach., New York, σελ. 10–19 
  12. ↑ Harry Bowen {Hunt III} (Αυγ. 1973). On the Time and Tape Complexity of Languages (PDF) (Ph.D. thesis). TR. 73-182. Cornell University. 
  13. ↑ Hopcroft, Ullman (1979), Theorem 13.15, p.351
  14. ↑ A.R. Meyer and L.J. Stockmeyer (Οκτ 1972). 13th Annual IEEE Symp. on Switching and Automata Theory (PDF). σελίδες 125—129. 
  15. ↑ L.J. Stockmeyer and A.R. Meyer (1973). Proc. 5th ann. symp. on Theory of computing (STOC) (PDF). ACM. σελίδες 1—9. 
  16. ↑ Furst, M.; Saxe, J. B.; Sipser, M. (1984). «Parity, circuits, and the polynomial-time hierarchy». Math. Systems Theory 17: 13–27. doi:10.1007/bf01744431. 
  17. ↑ Cook, Stephen· Nguyen, Phuong (2010). Logical foundations of proof complexity (1. publ. έκδοση). Ithaca, NY: Association for Symbolic Logic. σελ. 75. ISBN 0-521-51729-X. 
  18. ↑ J. Hartmanis, P. L. Lewis II, and R. E. Stearns.
  19. ↑ How to prove that a language is not regular?
  20. ↑ A finite language shouldn't be confused with a (usually infinite) language generated by a finite automaton.
  21. ↑ Volker Diekert, Paul Gastin (2008). «First-order definable languages». Στο: Jörg Flum, Erich Grädel, Thomas Wilke. Logic and automata: history and perspectives (PDF). Amsterdam University Press. ISBN 978-90-5356-576-6. CS1 maint: Πολλαπλές ονομασίες: editors list (link)
  22. ↑ Honkala, Juha (1989). «A necessary condition for the rationality of the zeta function of a regular language». Theor. Comput. Sci. 66 (3): 341–347. doi:10.1016/0304-3975(89)90159-x. Zbl 0675.68034. http://www.sciencedirect.com/science/article/pii/030439758990159X/pdf?md5=70fbb58e4c5fe963531adf8e258edd0f&pid=1-s2.0-030439758990159X-main.pdf. 
  23. ↑ Berstel & Reutenauer (2011) p.220

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

Ανακτήθηκε από "https://el.wikipedia.org/w/index.php?title=Κανονική_γλώσσα&oldid=10114218"