Οι γλώσσες που μπορεί να παραχθούν από κανονικές εκφράσεις είναι αυτές που αναγνωρίζονται από πεπερασμένα αυτόματα. Όμως απλές γλώσσες, δεν μπορούν να προκύψουν από αυτόν τον τρόπο και συνεπώς θα πρέπει να βρούμε ένα άλλο τρόπο υπολογισμού τους.

Γλώσσες της μορφής L{0^n 1^n}  απαιτούν την δημιουργία μιας γραμματικής από την οποία θα μπορεί να παραχθεί ένα σύνολο συμβολοσειρών , με μια βασική ιδέα, η οποία ξεκινά από μια αρχική μεταβλητή S και χρησιμοποιώντας κανόνες αντικατάστασης μεταβλητών μπορούμε να παράγουμε συμβολοσειρές που θα περιέχουν μόνο τερματικά σύμβολα.  Αυτές οι γραμματικές αναφέρονται και ως Γραμματικές Ανεξάρτητες Συμφραζομένων.

Για παράδειγμα ας εξετάσουμε την γλώσσα L{0^n 1^n} .

Αν n=0 τότε η συμβολοσειρά ε ανήκει στην L. 

Ακόμα για μία αρχική μεταβλητή S, με 0S1 ανήκει στην L. Άρα οι κανόνες παραγωγής της L θα είναι

S--> ε

S-->0S1

Όπου --> σημαίνει "παράγει" ή "παίρνει τιμή".

Έτσι μια συμβολοσειρά της μορφής 00001111 που ανήκει στην L θα παράγεται από τους παραπάνω κανόνες ως εξής .

S-->0S1 --> 00S11 --> 000S111 --> 0000S1111 --> 0000ε1111 --> 00001111

Τα 0 και 1 θεωρούνται τερματικά σύμβολα, ενώ στην συμβολοσειρά 00S11 ονομάζονται συμφραζόμενα, και κατά συνέπεια μπορούμε να αντικαταστήσουμε την S ανεξάρτητα από τις συμβολοσειρές που την περιβάλλουν. Με αλλά λόγια η γραμματική μας είναι ανεξάρτητη συμφραζομένων. Τέτοιες εκφράσεις αναγνωρίζονται από αυτόματα που πρέπει να διαθέτουν μια μορφής "μνήμης" που να εκφράζει τον άπειρο αριθμό των καταστάσεων τους σε πεπερασμένο χώρο. Αυτό το πετυχαίνουμε με τα αυτόματα στοίβας η σωρού. Περισσότερα για τα αυτόματα αυτά μπορείτε να διαβάσετε στο παρακάτω pdf.

Για την απόδειξη, μιας άπειρης γλώσσας ότι είναι Ανεξάρτητη Συμφραζομένων, και μπορεί να αναγνωριστεί από ένα αυτόματο στοίβας, χρησιμοποιούμε το Λήμμα Άντλησης. 

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

Λήμμα ´Αντλησης για Ανεξάτητων Συμφραζομένων.

Αν L άπειρη γλώσσα ΑΣ τότε , Υπάρχει p>0 ώστε κάθε S με S ανήκει στην L και  |S|≥ p τότε γράφεται στην μορφή S=uxyz όπου:

1) |xyz| ≤ p

2) |xz|>0

3) ux^m yz^m v ανήκει στην L για κάθε m≥ 0 

Ας δώσουμε ένα παράδειγμα εφαρμογής του λήμματος.

Έστω L ={0^k 1^m 2^n / k<m<n} είναι ΑΣ και p ο αριθμός του λήμματος άντλησης. Συνεπώς θα έχει την μορφή S= 0^p 1^p+1 2^p+2 με μήκος 3p+3>0.

Άρα η S γράφεται S= uxyz και θα είναι |xyz|≤ p (1) και |xz| >0 (2) τότε θα εξετάσουμε τις παρακάτω περιπτώσεις.

1η Περίπτωση 

Η xyz περιέχει σύμβολα από ένα μόνο τμήμα της S

i) Η xyz να έχει μόνο 0. Τότε η ux^2 yz^2 v από (1) έχει επιπλέον 0 από την S. 

Άρα τα 0 γίνονται ίσα ή περισσότερα από τα 1 δηλαδή ux^2 yz^2 v δεν ανήκει στην L.

ii) Αν η xyz έχει μόνο 1 τότε αναφερόμαστε ομοίως με την (i).

iii) Η xyz έχει μόνο 2. Τότε η ux^0 yz^0 v λόγω της (2) , έχει λιγότερα 2 από την S. Δηλαδή τα 2 δεν είναι περισσότερα από τους 1 οπότε ux^0 yz^0 v δεν ανήκει στην L.

2η Περίπτωση

Η xyz περιέχει σύμβολα από δύο τμήματα της S.

i) Η xyz περιέχει  0 και 1. Τότε η ux^2 yz^2 v έχει παραπάνω 1 ή 0 από την S. Αν έχει παραπάνω 1 τότε γίνονται τουλάχιστον ίσα με τα 2. Σε περίπτωση που έχει παραπάνω 0, τότε τα 0 θα γίνονται τουλάχιστον ίσα με τα 1. Άρα η ux^2 yz^2 v δεν ανήκει στην L. 

ii) Η xyz περιέχει 1 και 2. Τότε η ux^0 yz^0 v  θα έχει λιγότερα 1 ή 2 από την S. Αν δεν έχει λιγότερα 1 τότε θα έχει λιγότερα 2 . Δηλαδή τα 2 θα είναι περισσότερα από τα 1, οπότε η 

ux^0 yz^0 v δεν ανήκει στην L.  Ομοίως στην περίπτωση που έχει λιγότερα 1 από τα 0. 

Άρα σε κάθε περίπτωση υπάρχει m≥0 τέτοιο ώστε  η ux^m yz^m v δεν ανήκει στην L. Η πρόταση αυτή μας οδηγεί σε άτοπο, κατά συνέπεια η L δεν είναι ανεξάρτητη συμφραζομένων.