Κάνοντας μια ανασκόπηση στις κανονικές γλώσσες θα μπορούσαμε να αναφέρουμε ότι οι κανονικές γλώσσες είναι κλειστές κάτω από οποιαδήποτε πράξη.
Δηλαδή αν L1,L2 κανονικές τότε : L1 *,L2 * , L1L2, L2,L1, L1 ∪ L2, L1 ∩L2, L1\L2, L2\L1, L1^- L2^- είναι κανονικές.
Ένα ακόμα στοιχείο που θα πρέπει να θυμόμαστε είναι ότι για μια κανονική γλώσσα L η οποία έχει n πλήθος διακρινόμενων ανά δύο συμβολοσειρών, τότε το ντετερμινιστικό αυτόματο που αντιστοιχεί στην γλώσσα θα έχει τουλάχιστον n καταστάσεις. Οι διακρινόμενες συμβολοσειρές είναι και έμμεσος τρόπος για να δείξουμε ότι μια γλώσσα δεν είναι κανονική.
Σε αυτό το σημείο ας υπενθυμίσουμε τον ορισμό των διακεκριμένων συμβολοσειρών.
Έστω γλώσσα L με αλφάβητο Σ. Δύο συμβολοσειρές x ,y που ανήκουν στο Σ* είναι διακρινόμενες μεταξύ τους ως προς την L όταν υπάρχει z συμβολοσειρά που ανήκει στο Σ* έτσι ώστε:
xy ανήκει στην L και yz δεν ανήκει στην L.
Για παράδειγμα, θεωρείστε γλώσσα L={x∈ {0,1}*/ η x περιέχει 111}
Αν x =11 και y=1 τότε θεωρώ z=1 και θα είναι : xy= 111 ανήκει L και yz=11 δεν ανήκει L. Συνεπώς οι x,y είναι διακρινόμενες μεταξύ τους ως προς L. το σύνολο των διακρινόμενων ανά δύο συμβολοσειρές ως προς L είναι {ε, 1, 11, 111}. Οι διακρινόμενες συμβολοσειρές αντιπροσωπεύουν και τις καταστάσεις του αυτόματου.
Λήμμα Άντλησης
Έστω L άπειρη κανονική γλώσσα. Τότε υπάρχει φυσικός p >0 ώστε κάθε συμβολοσειρά s που ανήκει στην L με |s|≥ p γράφεται στην μορφή s= xyz τέτοια ώστε να ισχύει:
1. |xy|≤ p
2. y ≠ ε ή |y|>0
3. x y^m z ∈ L για κάθε m ≥ 0
Θα δώσουμε ένα παράδειγμα για το πως δουλεύουμε με το Λήμμα Άντλησης, και θα δείξουμε ότι η γλώσσα
L={x= 0^n 1^n / n≥0} δεν είναι κανονική.
Υπόθεση: Έστω L κανονική και p ο αριθμός του λήμματος άντλησης.
Θεωρώ τη συμβολοσειρά s= 0^p 1^p ∈L και |s|=2p>p άρα s= xyz
όπου |xy|≤ p (1) και y ≠ ε(2).
H s μπορεί να έχει την παρακάτω μορφή
s= 000....0001 11...111
| xy | z |
Η xy λόγω της (1) περιέχει μόνο 0 από το πρώτο τμήμα της s. Δηλαδή
xy=0^i με 0<i ≤p και y=0^j με 0<j≤ i λόγω του (2) του λήμματος.
Η z περιέχει τα 0 που περισσεύουν από την xy και όλους τους άσσους.
Δηλαδή θα είναι z= 0^p-i 1^p
Θεωρώ συμβολοσειρά x y^2 z = (xy)(y)(z)= 0^i 0^j 0^p-i 1^p = 0^i+j+p-i 1^p = 0^p+j 1^p ∉ L
για j>0 και p+j>p Άτοπο, άρα η L δεν είναι κανονική.
Με απλά λόγια περιγράφοντας το προηγούμενο παράδειγμα θα λέγαμε ότι, η y περιέχει μόνο μηδέν από το πρώτο τμήμα της s. Η x y^2 z περιέχει περισσότερα μηδέν από την s κατά συνέπεια περιέχει και περισσότερα 0 από 1. Δηλαδή η x y^2 z ∉ L άτοπο, άρα L δεν είναι κανονική.
Περισσότερα για τις κανονικές γλώσσες θα βρείτε και στην σελίδα μας Tutorial/Κανονικές Γλώσσες
1. |xy|≤ p
2. y ≠ ε ή |y|>0
3. x y^m z ∈ L για κάθε m ≥ 0
Θα δώσουμε ένα παράδειγμα για το πως δουλεύουμε με το Λήμμα Άντλησης, και θα δείξουμε ότι η γλώσσα
L={x= 0^n 1^n / n≥0} δεν είναι κανονική.
Υπόθεση: Έστω L κανονική και p ο αριθμός του λήμματος άντλησης.
Θεωρώ τη συμβολοσειρά s= 0^p 1^p ∈L και |s|=2p>p άρα s= xyz
όπου |xy|≤ p (1) και y ≠ ε(2).
H s μπορεί να έχει την παρακάτω μορφή
s= 000....0001 11...111
| xy | z |
Η xy λόγω της (1) περιέχει μόνο 0 από το πρώτο τμήμα της s. Δηλαδή
xy=0^i με 0<i ≤p και y=0^j με 0<j≤ i λόγω του (2) του λήμματος.
Η z περιέχει τα 0 που περισσεύουν από την xy και όλους τους άσσους.
Δηλαδή θα είναι z= 0^p-i 1^p
Θεωρώ συμβολοσειρά x y^2 z = (xy)(y)(z)= 0^i 0^j 0^p-i 1^p = 0^i+j+p-i 1^p = 0^p+j 1^p ∉ L
για j>0 και p+j>p Άτοπο, άρα η L δεν είναι κανονική.
Με απλά λόγια περιγράφοντας το προηγούμενο παράδειγμα θα λέγαμε ότι, η y περιέχει μόνο μηδέν από το πρώτο τμήμα της s. Η x y^2 z περιέχει περισσότερα μηδέν από την s κατά συνέπεια περιέχει και περισσότερα 0 από 1. Δηλαδή η x y^2 z ∉ L άτοπο, άρα L δεν είναι κανονική.
Περισσότερα για τις κανονικές γλώσσες θα βρείτε και στην σελίδα μας Tutorial/Κανονικές Γλώσσες