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

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

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

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

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

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

Ένα απλό παράδειγμα γλώσσας που δεν είναι κανονική αποτελεί το σύνολο των συμβολοσειρών  { anbn | n ≥ 0 }Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).. Εμπειρικά, η γλώσσα αυτή δεν μπορεί να αναγνωριστεί από ένα πεπερασμένο αυτόματο διότι αυτό έχει πεπερασμένη μνήμη και δεν είναι ικανό να θυμάται το ακριβές πλήθος των a. Σε επόμενη παράγραφο παρουσιάζονται τεχνικές για συστηματική επαλήθευση αυτού του γεγονότος.

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

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

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

 Ιδιότητες κλεισίματος (closure) 
Οι κανονικές γλώσσες κλείνουν υπό τις διάφορες πράξεις, δηλαδή αν οι γλώσσες K και L είναι κανονικές, τότε το αποτέλεσμα των παρακάτω πράξεων αποτελεί επίσης κανονική γλώσσα:
 το σύνολο των θεωρητικών Boolean πράξεων: η ένωση K ∪ L, η τομή K ∩ L και το συμπλήρωμα  L, καθώς και το σχετικό συμπλήρωμα K-L.Salomaa (1981) p.28
 οι κανονικές πράξεις: K ∪ L,συνένωσηΚ ∘ L, και το άστρο του Kleene L*.Salomaa (1981) p.27
 Οι trio πράξεις: ομομορφισμός συμβολοσειράς, αντίστροφος ομομορφισμός συμβολοσειράς και τομή με κανονικές γλώσσες.
 η αντιστροφή (ή καθρεπτισμός) LR.

 Ιδιότητες αποφασισιμότητας 
Δοθέντων δύο ντετερμινιστικών πεπερασμένων αυτομάτων Α και Β, μπορεί να αποφασιστεί εάν αποδέχονται την ίδια γλώσσα. Ως επακόλουθο, με χρήση των παραπάνω ιδιοτήτων κλεισίματος, μπορούμε να αποφανθούμε και για τα ακόλουθα προβλήματα, δοθέντων τυχαίων ντετερμινιστικών πεπερασμένων αυτομάτων Α και Β που αποδέχονται τις γλώσσες LA και LB αντίστοιχα:
 Περιέχεται η μια γλώσσα στην άλλη: LA ⊆ LB ;
 Είναι οι γλώσσες ασυμβίβαστες: LA ∩ LB = {};
 Είναι κάποια γλώσσα κενή: LA = {};
 Είναι κάποια γλώσσα καθολική: LA = Σ*;
 Ανήκει μια συμβολοσειρά σε κάποια γλώσσα: αν a ∈ Σ*, τότε είναι a ∈ LB;
Για τις κανονικές εκφράσεις, το πρόβλημα της καθολικότητας είναι NP-complete ακόμη και για αλφάβητο με ένα στοιχείο. Για μεγαλύτερα αλφάβητα, το πρόβλημα γίνεται PSPACE-complete. Αν οι κανονικές εκφράσεις επεκταθούν ώστε να επιτρέπουν κι έναν τελεστή τετραγώνου, με το "A2" να είναι ισοδύναμο με το "AA", τότε και πάλι μόνο κανονικές γλώσσες μπορούν να περιγραφούν, αλλά το πρόβλημα της καθολικότητας αποκτά ένα εκθετικό χωρικό κάτω φράγμαHopcroft, Ullman (1979), Theorem 13.15, p.351

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

Αν μια γλώσσα δεν είναι κανονική, τότε απαιτεί μια μηχανή με τουλάχιστον Ω(log log n) χώρο για την αναγνώριση (όπου n το μέγεθος της εισόδου)J. Hartmanis, P. L. Lewis II, and R. E. Stearns.. Με άλλα λόγια, το DSPACE(o(log log n)) ισοδυναμεί με την κλάση των κανονικών γλωσσών. Στην πράξη, τα περισσότερα μη κανονικά προβλήματα επιλύονται από μηχανές που καταλαμβάνουν τουλάχιστον λογαριθμικό χώρο.

 Θέση στην ιεραρχία του Chomsky 
μικρογραφία|250x250εσ|Η κανονική γλώσσα στις κλάσεις της ιεραρχίας Chomsky.
Για να εντοπίσουμε τις κανονικές γλώσσες στην ιεραρχία Chomsky, παρατηρούμε αρχικά ότι κάθε κανονική γλώσσα είναι ελεύθερη συμφραζομένων (context-free). Το αντίστροφο δεν ισχύει· για παράδειγμα, η γλώσσα που αποτελείται από όλες τις συμβολοσειρές με ίσο αριθμό a και b είναι γλώσσα χωρίς συμφραζόμενα, αλλά όχι κανονική. Για να αποδείξουμε ότι μια τέτοια γλώσσα δεν είναι κανονική, συχνά χρησιμοποιούμε το θεώρημα Myhill-Nerode ή το pumping lemma ανάμεσα σε άλλες μεθόδουςHow to prove that a language is not regular?.

Κάποιες σημαντικές υπο-κλάσεις των κανονικών γλωσσών είναι:
 Πεπερασμένες γλώσσες - εκείνες που περιέχουν μόνο ένα πεπερασμένο πλήθος λέξεωνA finite language shouldn't be confused with a (usually infinite) language generated by a finite automaton.. Αυτές είναι κανονικές γλώσσες, αφού μπορούμε να δημιουργήσουμε μια κανονική έκφραση με την ένωση κάθε λέξης στη γλώσσα.
 Star-free γλώσσες, οι οποίες μπορούν να περιγραφούν από μια κανονική έκφραση που κατασκευάζεται από το κενό σύμβολο, γράμματα, συνένωση και όλους τους Boolean τελεστές περιλαμβανομένου του συμπληρώματος, αλλά όχι του Άστρου του Kleene: αυτή η κλάση περιλαμβάνει όλες τις πεπερασμένες γλώσσες. 
 Κυκλικές γλώσσες, που ικανοποιούν τις συνθήκες uv ∈ L ⇔ vu ∈ L και w ∈ L ⇔ w n ∈ L.Berstel & Reutenauer (2011) p.220

 Παραπομπές 




  Chapter 1: Regular Languages, pp. 31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp. 152–155.
 Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics: Symbolic Combinatorics.  Online book, 2002.



 Εξωτερικοί σύνδεσμοι 
 Complexity Zoo: Class REG 

Κατηγορία:Τυπικές γλώσσες