Γενικά μια γλώσσα είναι κανονική αν υπάρχει μια κανονική έκφραση που να την περιγράφει.
Με άλλα λόγια μια γλώσσα L λέγεται κανονική αν υπάρχει κανονική έκφραση R με L = L(R).
Κάθε πεπερασμένη γλώσσα μπορεί να αναπαρασταθεί με μια απλή απαρίθμηση όλων των συμβολοσειρών που ανήκουν σε αυτή, ενώ μια κανονική έκφραση μπορεί να θεωρηθεί ως μια τυπική συμβολοσειρά της γλώσσας που εκπροσωπεί. Πιο πολύπλοκες εκφράσεις αλλά και γλώσσες μπορούν να φτιαχτούν χρησιμοποιώντας τις βασικές πράξεις πάνω σε απλούστερες εκφράσεις.
Αυτή την αναδρομική έννοια την εκφράζουμε με τον παρακάτω ορισμό
Η Rείναι μια κανονική έκφραση αν είναι της μορφής
1. a, όπου a ένα σύμβολο του αλφάβητου Σ,
2. ε,
3. ∅,
4. (R1 ∪ R2), όπου R1 και R2 δύο κανονικές εκφράσεις,
5. (R1 R2), όπου R1 και R2 δύο κανονικές εκφράσεις,
6. (R1*), όπου R1 μια κανονική έκφραση.
Συντομογραφία: R+ = RR*
Από τον παραπάνω ορισμό απορρέουν και τα βασικά θεωρήματα:
- Οι κανονικές γλώσσες είναι κλειστές ως προς τις πράξεις της ένωσης, της συνένωσης και το αστεριού Kleene.
- Κάθε πεπερασμένη γλώσσα είναι κανονική.
- Μια γλώσσα είναι κανονική αν και μόνο αν υπάρχει κανονική έκφραση που την περιγράφει.
Θα δώσουμε μερικά παραδείγματα για να γίνει πιο κατανοητό.
- Αν (0 ∪ 1)0* τότε θα ήταν είναι η γλώσσα που περιέχει όλες οι λέξεις που ξεκινούν
με 0 ή 1 ακολουθούμενες από οποιοδήποτε πλήθος από 0.
- Έστω L={x∈ {a,b}* | η x περιέχει το ba και τελειώνει σε b}. Η L μπορεί να περιγραφεί ως εξής {a, b}* {ba} {a, b}* {b}
Δηλαδή ότι πριν και μετά από το ba μπορεί να υπάρχει οτιδήποτε από a ή b ή τίποτα , ενώ υποχρεωτικά ακολουθεί το b στο τέλος.
Συνεπώς η κανονική έκφραση θα είναι L= (a+b)* ba (a+b)* b
Πιο αναλυτικά θα λέγαμε ότι μια κανονική έκφραση και κατά συνέπεια μια κανονική γλώσσα θα πρέπει να αναγνωρίζεται από ένα αυτόματο είτε αυτό είναι ένα Ντετερμινιστικό Αυτόματο(DFA) ή από ένα Μη Ντετερμινιστικό Αυτόματο(NFA). Τα αυτόματα γενικά είναι αφηρημένες μηχανές για την μελέτη μαθηματικών αντικειμένων και των υπολογιστικών προβλημάτων που μπορούν να λυθούν με αυτά. Το αυτόματο αποτελείται από καταστάσεις (που απεικονίζονται με κύκλους), και μεταβάσεις (που απεικονίζονται με βέλη). Καθώς το αυτόματο βλέπει ένα σύμβολο εισόδου, εκτελεί μια μετάβαση σε άλλη κατάσταση, ανάλογα με τη συνάρτηση μετάβασης- δ (η οποία δέχεται την τρέχουσα κατάσταση και το τελευταίο σύμβολο ως εισόδους).
Γενικά θα πρέπει να συγκρατήσετε τα εξής:
- Μια γλώσσα αναγνωρίζεται από ένα DFA αν και μόνο αν υπάρχει κανονική έκφραση που την περιγράφει.
- Μια γλώσσα αναγνωρίζεται από ένα ΝFA αν και μόνο αν υπάρχει κανονική έκφραση που την περιγράφει.