Exercici 1.9 Trobeu una gramàtica que genere cadenes en en les quals hi haja el doble de zeros que duns.
Exercici 1.10 Elimineu les regles nul·les en la gramàtica següent:
Exercici 1.11 Calculeu el llenguatge generat per la gramàtica següent i trobeu una gramàtica equivalent tan senzilla com siga possible. De quin tipus és el llenguatge?
Exercici 1.12 Justifiqueu que el llenguatge és generat per la gramàtica
Exercici 1.13 Trobeu gramàtiques independents del context que generen els llenguatges següents:
Exercici 1.14 Trobeu el llenguatge generat per la gramàtica següent i justifiqueu la resposta.
Exercici 1.15 Digueu quin és el llenguatge generat per la gramàtica
Exercici 1.16 Trobeu el llenguatge generat per la gramàtica
Exercici 1.17 Comproveu que el llenguatge és generat per la gramàtica
Suggeriment: considereu les formes sentencials
1 No els nombres mateixos, sinó entesos com a símbols escrits en un paper, per exemple.
2 Hem utilitzat el símbol per fer més clara la separació en símbols de la cadena. Una altra pràctica habitual en aquests casos és envoltar els símbols amb i. Aleshores escriuríem la cadena com a
3 Fem notar que aquest conjunt és infinit.
4 En altres texts sescriu també com a λ.
5 Loperació concatenació sestén trivialment al cas de llenguatges definint
6 Com es fa en els diccionaris.
7 Recordem que, matemàticamente un homomorfisme (o morfisme) és tota aplicació f entre dos conjunts amb lleis de composició interna,(A, +) i (B, ×), que compleix que f(x + y) = f(x) × f(y) per a tot parell delements de A. En aquest sentit també són homomorfismes les substitucions.
8 Aquesta demostració de no numerabilitat es dóna al final de lapèndix A.
9 Hem decidit en aquest manual utilitzar la nomenclatura contextual i incontextual en lloc de la més correcta sensible al context i de context lliure. Així, doncs, cal tenir present que contextual o soposa a incontextual i és, per tant, diferent de no contextual.