Παρακάτω δίνονται οκτώ απλές γραμματικές, κάθε μία από τις οποίες παράγει μία άπειρη γλώσσα. Οι συμβολοσειρές των γλωσσών αυτών στις περισσότερες περιπτώσεις συνδυάζουν εναλλαγές των a και b, παρόλο που υπάρχουν εξαιρέσεις και δεν παράγονται όλες οι συμβολοσειρές αυτής της μορφής από όλες τις γραμματικές.
- G1: S → abS | ab
- G2: S → SS | ab
- G3: S → aB; B → bS | a
- G4: S → aB; B → bS | b
- G5: S → aB; B → bS | ab
- G6: S → aB | b; B → bS
- G7: S → aB | a; B → bS
- G8: S → aB | ab; B → bS
Σε όλες τις περιπτώσεις το αρχικό σύμβολο είναι το S. Βρείτε τη γλώσσα της κάθε μιας από τις παραπάνω γραμματικές. Στη συνέχεια, αναγνωρίστε από την παρακάτω λίστα ένα ζεύγος γραμματικών που ορίζει την ίδια γλώσσα.