on A és qualsevol símbol no terminal i a és qualsevol cadena de V*.
tipus 3 o també gramàtiques regulars. Les produccions han de ser de la forma
on A i B són símbols no terminals i a pot ser qualsevol cadena de terminals. Aquestes gramàtiques shaurien danomenar propiament gramàtiques regulars per la dreta. Es poden definir de la mateixa manera les gramàtiques regulars per lesquerra exigint que les produccions siguen de la forma ABa en comptes de AaB com en la definició anterior. Es pot demostrar que ambdós tipus de gramàtiques són equivalents, en el sentit que per a tota gramàtica dun tipus nhi ha una de laltre tipus que és equivalent. En aquest manual parlarem únicament de gramàtiques regulars i ens referirem sempre a les regulars per la dreta si no especifiquem el contrari.
Els quatre tipus de gramàtiques introduits indueixen quatre families de llenguatges segons el tipus de gramàtiques amb què es puguen generar.
Es diu que un llenguatge és de tipus N (N = 0,1,2,3) si hi ha alguna gramàtica de tipus N que el genere.
Com a conseqüència daquesta definició sobtenen quatre classes de llenguatges incloses les unes dins de les altres com es mostra en la figura 1.1. Escriurem la classe formada pels llenguatges de tipus N com a N. Les classes de llenguatges de tipus 1, 2 i 3, les escriurem també com a R, I i C, respectivament.
Figura 1.1: Relació entre les diferents classes de llenguatges induïdes per la jerarquia de Chomsky.
Donada una classe de llenguatges qualsevol, , es defineix la classe co com a
Per exemple, la classe dels llenguatges co-regulars, o co-R, està formada per llenguatges els complementaris dels quals són regulars.
Un altre parell de classes que són interessants (ser la seua simplicitat) són els llenguatges finits i els co-finits. Es pot demostrar molt fàcilment (i es deixa com a exercici) que tot llenguatge finit és regular.
1.2.2 Transformació de gramàtiques
Les produccions de les gramàtiques es poden manipular de diverses maneres, de forma que el llenguatge generat no canvia. En el cas particular de les gramàtiques incontextuals hi ha algunes operacions especialment interessants.
Substitució o desplegament
Siga A un símbol no terminal duna gramàtica incontextual i siga
el conjunt de produccions que tenen A com a part esquerra.
Donada una producció de G de la forma X αAß amb X A, es pot substituir per
La gramàtica resultant és equivalent, ja que cada una daquestes noves produccions representa lefecte de dues produccions originals. Remarquem el fet que les produccions de Pa segueixen estant en la nova gramàtica i que només X y αAß ha desaparegut.
Aquesta transformació es pot fer servir per eliminar les anomenades regles de redenominació de la forma A B. Per exemple, la gramàtica
S AB\Aa\bA
A Aab\Aba\ε
B bB\b\A
és equivalent a
S AB\Aa\bA
A Aab\Aba\ε
B bB\b\Aab\Aba\ε
Factorització
Siga un conjunt de produccions de la forma
de manera que totes les parts esquerres coincideixen i les parts dretes comparteixen un determinat prefix a. Aquestes produccions es poden, doncs, substituir per
on B és un nou símbol no terminal.
Eliminació duna producció
Siga una producció no recursiva i P el conjunt de produccions en les quals A apareix en la part dreta. Aleshores, la producció es pot eliminar si per cada producció de de la forma X αAß se nafegeix una altra X αγß.
La gramàtica resultant és equivalent, ja que les noves produccions reprodueixen lefecte de les originals (que no desapareixen) juntament amb el de la producció .
Un cas particular daquest és leliminació de regles nul·les de la forma A ε amb A S.
Per exemple, donada la gramàtica
S abA\baB\a
A bB\abA\ε
B aA\baB\ε
es pot convertir en la gramàtica següent eliminant les dues regles nul·les.
S abA\baB\ab\ba\a
A bB\abA\b\ab
B aA\baB\a\ba
Modificació de bucles
Un bucle simple en una gramàtica incontextual consisteix en dos conjunts de produccions associades a un mateix símbol. En el primer conjunt apareix aquest símbol i en el segon conjunt no. Si aquest símbol apareix en la part dreta en la posició més a lesquerra es parla de bucle a esquerres o recursivitat a esquerres.
i si apareix en la posició més a la dreta es parla de bucle a dretes o recursivitat a dretes.
Sempre es pot substituir un tipus de recursivitat per laltre sense que el llenguatge es modifique. Per exemple, la recursivitat a dretes anterior es pot substituir per les produccions següents: