Αυτόματα, Κανονικές Γλώσσες και Εκφράσεις.
Τα αυτόματα είναι ένα είδος μηχανής ή προσομοιώνουν την λειτουργία της όταν διέρχεται από ένα πεπερασμένο σύνολο καταστάσεων. Κάθε αυτόματο δεν χρειάζεται να θυμάται όλη την συμβολοσειρά εισόδου που έχει διαβάσει αλλά μόνο την κατάσταση στην οποία βρίσκεται.
Η κατασκευή ενός αυτόματου έχει σκοπό να αναγνωρίζει ένα πεπερασμένο σύνολο από χαρακτήρες (αλφάβητο) που αποτελούν και την Γλώσσα (L) του αυτόματου. Κάθε πεπερασμένη γλώσσα
μπορεί να αναπαρασταθεί με μια απλή απαρίθμηση όλων των συμβολοσειρών που ανήκουν σε αυτή. Τότε μιλάμε για μια Κανονική Γλώσσα, και το πλήθος των συμβολοσειρών που μπορεί να περιγραφούν από αυτή θα αποτελούν την Κανονική Έκφραση.
μπορεί να αναπαρασταθεί με μια απλή απαρίθμηση όλων των συμβολοσειρών που ανήκουν σε αυτή. Τότε μιλάμε για μια Κανονική Γλώσσα, και το πλήθος των συμβολοσειρών που μπορεί να περιγραφούν από αυτή θα αποτελούν την Κανονική Έκφραση.
Χρήσιμο συμπέρασμα λοιπόν είναι ότι μια γλώσσα θα είναι κανονική αν και μόνο αν μπορεί να αναγνωριστεί από ένα πεπερασμένο αυτόματο.
Συμβολισμοί :
Αλφάβητο Σ={0,1} δηλαδή το αλφάβητο αποτελείτε από δύο χαρακτήρες το μηδέν και ο άσσος.
Η Γλώσσα L={ x {0,1} * | η x τελειώνει με 1 και δεν περιέχει το 00} παράγει για παράδειγμα μια Συμβολοσειρά : 010101010101010101
Η Κενή συμβολοσειρά περιγράφεται με το γράμμα ε
Ο Αστερίσκος * μέσα στις κανονικές εκφράσεις δηλώνει ότι το σύνολο των συμβολοσειρών μπορεί να περιέχει την μηδενική συμβολοσειρά ή περισσότερα σύμβολα (loop).
Για παράδειγμα α* δηλώνει ότι μπορεί να έχει μηδέν ή περισσότερα α .
Για παράδειγμα α* δηλώνει ότι μπορεί να έχει μηδέν ή περισσότερα α .
Εκφράσεις αα* δηλώνουν ότι μπορεί να περιέχουν τουλάχιστον ένα α. Η ισοδύναμη έκφραση είναι α+ .