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:
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:
La conversió en sentit contrari es faria igualment.
1.2.3 Verificació de gramàtiques
Les gramàtiques consitueixen una eina fonamental per a descriure de manera compacta i clara llenguatges que són intrínsecament complexos. No obstant això, de vegades pot resultar complicat establir lequivalència entre el llenguatge generat per una gramàtica i el llenguatge expressat mitjançant algun altre formalisme. El fet de demostrar rigorosament lequivalència entre un llenguatge descrit formalment i una gramàtica sanomena verificar la gramàtica.
Aquesta verificació requereix normalment algun tipus de demostració per inducció donada la natura recursiva de les gramàtiques. En aquest manual, no verificarem normalment les gramàtiques, ja que lequivalència entre aquestes i els corresponents llenguatges estarà suficientment clara.
Exemple 1.1Demostrar que el llenguatge L format per les cadenes w ϵ {0,1}* que compleixen |w|0 = 2k + 1 per a algun enter k, és generat per la gramàtica donada per
S 1S|0A
A L4|0S|ε
Primer cal demostrar que L(G) C L, per a la qual cosa cal caracteritzar les cadenes que genera G.
Per inspecció de les produccions associades a S és evident que
Pel mateix motiu, les produccions associades a a porten a
Combinant els dos resultats anteriors
Per tant, es pot afirmar que
don es conclou que L(G) L.
En segon lloc, cal demostrar també que L L(G). És a dir, que ,
Ho demostrarem per inducció en la talla de w.
B.I. Lúnica cadena de L de talla menor o igual que 1 és 0, i es compleix
H.I.
P.I. Siga w amb |w| = n i |w|0 = 2k + 1. Hi haurà dos casos:
1. w = lx i aleshores x compleix la hipótesi dinducció i per tant
2. w = 0x. x tindrà un nombre parell de zeros i hi haurà dos subcasos:
(a) x = 1i es té que
(b) x = 1i 0y on y ha de contenir necessàriament 2l + 1 zeros i compleix la hipótesi dinducció. Aleshores,
En els dos casos es pot trobar una derivació i aleshores es pot concloure
que
i per tant L L(G).
1.3 Acceptació de llenguatges i computabilitat
De la mateixa manera que sha estudiat laspecte generatiu dels llenguatges es pot plantejar el problema contrari. És a dir, donada una cadena x qualsevol i una descripció (finita) dun llenguatge, pertany la cadena x a aquest llenguatge?
Aquesta pregunta es pot plantejar per a descriptions de llenguatges mijantçant gramàtiques, però el problema no és gens trivial fins i tot per a llenguatges relativament senzills.
Per aquesta raó és convenient definir el que sanomenen acceptors o autòmats, que es poden veure com a dispositius lògics que processen cadenes i decideixen sobre aquestes (les accepten o no). Això no és més que una altra forma de descriure llenguatges. Donat qualsevol autòmat no trivial, es pot definir el llenguatge associat a lautòmat com aquell que està format per les cadenes que lautòmat accepta.
Definirem al llarg daquest manual una família dautòmats, el més general dels quals és el que es coneix com a màquina de Turing. Veurem que hi ha relacions estretes entre els diferents tipus dautòmats i les gramàtiques de la jerarquia de Chomsky. A més a més, sestudiarà la relació entre el tipus de processament que pot fer lautòmat més general i els límits del que es pot o no es pot computar des del punt de vista dobtenció de solucions algorísmiques a problemes.
1.4 Exercicis
Exercici 1.1 Justifiqueu la regularitat del llenguatge
Exercici 1.2 Demostreu que la classe dels llenguatges finits i la dels co-finits són disjuntes.
Exercici 1.3 Siguen Calculeu els llenguatges
Exercici 1.4 Trobeu una gramàtica (com més senzilla millor) que genere cadenes de zeros i uns que no tinguen dos símbols 1 consecutius. De quin tipus és el llenguatge generat?
Exercici 1.5 Trobeu gramàtiques que generen els llenguatges
Exercici 1.6 Escriviu una gramàtica que genere les cadenes de digits corresponents a nombres enters. Per exemple, 0, 1, 22, 2304 són correctes, però 0023 no.
Exercici 1.7 Escriviu una gramàtica que genere les cadenes de dígits corresponents a nombres decimals. Per exemple, 0, 12.3, 0.15, 0.0000032.
Exercici 1.8 Trobeu una gramàtica que genere cadenes en {0,1}* en les quals tot zero vaja necessàriament seguit dun 1.
Exercici 1.9 Trobeu una gramàtica que genere cadenes en en les quals hi haja el doble de zeros que duns.