Читать книгу Teoria d'autòmats i llenguatges formals - Francesc Josep Ferri Rabasa - Страница 10

1. Llenguatges formals i computació

Aquest manual té com a objectiu l’estudi dels llenguatges formals, així com dels seus generadors i acceptors, juntament amb l’estreta relació que hi ha entre els llenguatges formals i la teoria de la computació.

Aquest estudi té una formulació matemàtica molt clara a partir del concepte de símbol, les operacions que s’hi poden definir i les seues propietats. Per això, es dedica aquest capítol introductori a donar les definicions bàsiques relacionades amb els diferents aspectes dels llenguatges formals que es faran servir al llarg de tot el manual. A banda, en l’apèndix A s’ofereix una introducció als conceptes matemàtics més importants que es donaran per suposats.

1.1 Símbols, cadenes i llenguatges

Considerarem un conjunt finit i no buit de símbols que anomenarem alfabet o vocabulari. Per exemple {a, b, c}, {0,1,2,3,4,5,6,7,8,9}o { } serien alfabets vàlids. El conjunt de tots els nombres enters¹ no seria un alfabet vàlid.

Podem definir un símbol com una etiqueta o una entitat que no té, en principi, cap significat i que és indivisible. Una cadena (de símbols), també anomenada mot o paraula, és una successió finita de símbols d’un alfabet determinat.

Per exemple, aaabbba, 1024 i ², serien exemples de cadenes sobre cada un dels alfabets anteriors.

Cada cadena de símbols té associada una longitud, que es defineix com el nombre de símbols que formen una cadena. Les cadenes anteriors tenen longitud 7, 4 i 3, respectivament. Escriurem la longitud d’una cadena x com a |x|.

Estendrem la notació per referirnos al nombre de símbols d’un cert tipus que conté una cadena. Així, si x és una cadena sobre ∑ i A és un subconjunt de ∑, |x|_A representa el nombre de símbols del conjunt A que conté x. Per al cas particular que A només continga un simbol, a, escriurem |x|_a en lloc de |x|_{a}. Per exemple, si x = aaabbba és una cadena sobre {a, b, c}, |x|_a = 4, |x|_b = 3, |x|_c = 0, i |x|{_{a, b}} = |x| = 7.

Si anomenem P(∑) el conjunt de totes les possibles cadenes sobre un determinat alfabet³, podem definir certes operacions internes dins d’aquest, la més important de les quals és la concatenacio.

Siguen x i y dues cadenes sobre un determinat alfabet £, anomenem concatenacio de x amb y la cadena resultant de juxtaposar les dues cadenes (x a l’esquerra i y a la dreta), i la representem com x · y o simplement com a xy.

Es pot demostrar fàcilment que el conjunt P(∑) amb la operació • té estructura de monoide i, per tant, també de semigrup. L’element neutre d’aquest conjunt respecte de la concatenacio (que ho és per l’esquerra i per la dreta) és una cadena especial que no té cap símbol, anomenada cadena buida o cadena nul·la, i que escriurem en aquest manual⁴ com a ε.

Diem que una cadena y és prefix d’una altra cadena x si i només si existeix alguna cadena z tal que x = yz.

Diem que una cadena y és sufix d’una altra cadena x si i només si existeix alguna cadena z tal que x = zy.

Diem que una cadena y és factor (o infix o subcadena) d’una altra cadena x si i només si existeixen cadenes z i t tals que x = zyt.

Els prefixos i sufixos són casos particulars de factors. Es parla de factors (prefixos o sufixos) propis quan aquests són diferents de la cadena buida i de la cadena a que es refereixen.

Anomenem factorització de x una descomposició de la cadena x en un nombre finit de factors, x = y1 · y1 ··· yk.

Siga un determinat alfabet ∑, anomenem llenguatge tot conjunt de cadenes sobre ∑.

Alguns exemples de llenguatges sobre els alfabets anteriors serien

La talla o grandària d’un llenguatge, L, és la cardinalitat o nombre de cadenes corresponent, que escriurem com a |L| normalment. Les talles de cada un dels llenguatges que acabem de donar com a exemple serien ∞, 3 i 2, respectivament. Una forma més rigorosa d’expressar el primer d’aquests llenguatges és

Sobre qualsevol alfabet, hi ha sempre dos llenguatges especials que reben el nom de llenguatge buit i llenguatge format per la cadena buida i que s’escriuen com a ∅ i {ε}, respectivament.

Aquests dos llenguatges són els elements neutres dins del conjunt de tots els possibles llenguatges respecte a les operacions unió i concatenació de llenguatges⁵, respectivament.

Es pot demostrar que, respecte a aquestes dues operacions, el conjunt de tots els possibles llenguatges té estructura de monoide commutatiu o abelià i de monoide, respectivament.

Donat un alfabet ∑ qualsevol, s’hi suposa donada una relació d’ordre total que origina el que s’anomena ordenació alfabètica. A partir d’aquesta es pot definir una ordenació lexicogràfica o ordenació canònica del conjunt P(∑), que consisteix a ordenar-ne les cadenes de menor a major longitud i, dins d’una mateixa longitud, ordenar-les per ordre alfabètic⁶.

Aquesta ordenació del conjunt P(∑) fa que es puga establir una correspondència biunívoca o bijecció entre aquest conjunt i els nombres naturals, la qual cosa implica que P(∑) és sempre un conjunt numerable.

1.1.1 Operacions amb cadenes

A banda de la concatenació, es poden definir altres operacions amb cadenes.

Es defineix la potència i-èsima d’una cadena x com la concatenació de x amb ella mateixa i vegades. S’escriu

Es considera, per definició, que x0 = e.

La potència admet també una definició recursiva:

Compleix les propietats següents:

La inversió, revers o reflexió d’una cadena, que escriurem com a xR, és una altra cadena formada pels mateixos simbols però en ordre invers.

La inversió també admet la definició recursiva següent:

1.1.2 Operations amb llenguatges

Com que els llenguatges són conjunts (de cadenes), s’hi poden aplicar totes les operacions usuals sobre conjunts, com ara la unió, la intersecció, el complement i la resta. Aquestes operacions, les escriurem com a

A més a més, les operacions amb cadenes es poden estendre al cas de llenguatges, de la mateixa manera que s’ha fet amb la concatenació.

En general, donada qualsevol operació interna m-ària amb cadenes, O, la seua extensió a llenguatges és donada per

A banda, hi ha altres operacions especifiques amb llenguatges.

El quocient de dos llenguatges, L₁ i L₂, és donat pels prefixos d’aquelles cadenes de L₁ que es poden factoritzar com el mateix prefix seguit d’un sufix en L₂.

L’operació quocient també es pot definir per a cadenes:

Per exemple, abc/c = ab i abc/ac no està definit.

Aquesta operació també s’anomena quocient per la dreta i es pot veure com la inversa de la operació concatenació per la dreta.

La extensió a llenguatges es pot dur a terme com a quocient entre un llenguatge i una cadena

i també com a quocient entre dos llenguatges

Aquesta darrera definició és equivalent a la primera que s’ha donat.

Per exemple, si L1 = {an | n ≥ 0 i L₂= {an bm | n, m ≥ 0}, aleshores L₁/a = L₁, L₂//b = L₂ i L₂//a = L1.

De la mateixa manera es poden definir també els quocients per l’esquerra entre cadenes o llenguatges. En alguns textos els quocients entre z i y per la dreta i per l’esquerra s’escriuen com a zy^–1 i y^–1z, respectivament.

El quocient per l’esquerra entre una cadena x i un llenguatge L, x^–1 L, s’anomena derivada de L respecte de x i està format pels anomenats sufixos de x en L (també de vegades bons finals de x en L).

Per exemple, està format per cadenes de zero o més símbols b perqué són les úniques que afegides a ab estàn en

Anomenem substitució una funció que a cada símbol d’un alfabet ∑ li fa correspondre un llenguatge sobre un altre alfabet .

Matemàticament,

La substitució s’estén trivialment a cadenes. Donada una cadena, la substitució que s’hi aplique donarà com a resultat la concatenació de les substitucions sobre cada un dels seus símbols.

Perquè tinga sentit, cal definir la substitució sobre la cadena buida, que ha de donar lògicament la cadena buida.

Escrivint-ho recursivament:

També ho podem escriure com

Les substitucions s’estenen també trivialment per a llenguatges de la manera següent:

Un cas particular de substitució és l’homomorfisme⁷ que és una substitució en la qual es compleix que a tot símbol de ∑ li correspon (com a màxim) una única cadena de . És a dir, h: *. Normalment escriurem les substitucions com a f i els homomorfismes com a h.

Considerem com a exemple una substitució entre els alfabets {0,1} i {a, b, c} donada per

Aleshores es compliria que

Donat un homomorfisme h: , anomenem homomorfisme invers de la cadena y ∈ , i ho escrivim com a h^–1(y), el conjunt de cadenes de ∑* tals que transformades per h donen y. És a dir,

També es pot definir l’homomorfisme invers d’un llenguatge quasi de la mateixa manera.

Considerem com a exemple el llenguatge i l’homomorfisme donat per h(0) = ab, h (1) = b, h(2) = a, h(3) = cc. Aleshores es compleix que

Per a tot homomorfisme sempre es compleix que

i també

Per a l’exemple anterior es té que

És important adonar-se que la propietat anterior no es compleix si intercanviem l’ordre d’aplicacio de l’homomorfisme i l’invers. Seguint amb el mateix exemple, tenim que

Si de l’anterior definició s’exclou el terme L0, s’obté l’anomenat tancament positiu:

Si, abusant de la notació, considerem l’alfabet E com un llenguatge finit format per cadenes de longitud 1, podem escriure

Aquests dos conjunts reben el nom de monoide lliure i semigrup lliure engendrats per E. D’ara endavant utilitzarem aquests noms i la notació ∑* i ∑⁺ per referirnos a aquests conjunts.

En el context de la teoria de llenguatges formals només tenen importància els llenguatges que són infinits. Fins i tot dins d’aquests, els més importants són els que defineixen les cadenes que hi pertanyen en funció d’una certa estructura dins de les cadenes.

1.2 Generació de llenguatges

En el context de la teoria de llenguatges formals només tenen importància els llenguatges que són infinits. Fins i tot dins d’aquests, els més importants són els que defineixen les cadenes que i ertanyen en funció d’una certa estructura dins de les cadenes.

Un exemple d’aquest tipus de llenguatge és el que està format per aquelles cadenes sobre l’alfabet ∑_ex = {x, +, *, (, )} que són expressions aritmètiques vàlides (ben parentitzades). És a dir,

Encara que és ben clar quin és aquest llenguatge, no pot ser definit d’una forma compacta (amb una descripció finita) de la mateixa manera que s’ha fet en els exemples anteriors.

Una forma de definir aquest tipus de llenguatges és mitjançant una definició recursiva. Un mecanisme que permet introduir definicions recursives en el context de cadenes de símbols és donat pels sistemes de reescriptura, un cas particular dels quals són les gramàtiques.

Els elements de l’alfabet no terminal, VN, s’anomenen símbols no terminals, símbols auxiliars o, simplement, variables de la gramàtica.

Una producció α → ß significa que la cadena a es pot reescriure com a ß(es pot canviar l’una per l’altra). Ens referirem a α i a β com les parts esquerra i dreta de la producció, respectivament. Per representar de forma compacta diverses produccions amb la mateixa part esquerra escriurem

en lloc de

Diem que una cadena y deriva directament d’una cadena x segons una gramàtica G, i ho escrivim com a si i només si , de forma que

Diem que una cadena y deriva d’una cadena x segons una gramàtica, i ho escrivim com a si i només si x = y o si existeix una seqüència finita de paraules tal que

Si, pel context, està clar a quina gramàtica ens estem referint, suprimirem la referència a la gramàtica ∈ en el símbol ⇒.

Les cadenes de V que es poden derivar a partir de l’axioma reben el nom de formes sentencials de G. Si, a més a mes, són cadenes exclusivament de Vt es diu que són sentències de G.

Per exemple, el llenguatge L_ex és generat per la gramàtica

on P és

Un exemple de derivació amb aquesta gramàtica seria

En aquest exemple hem subratllat en cada forma sentencial els símbols no terminals sobre els quals s’aplica la producció següent (la producció que s’aplica és òbvia per inspecció de la cadena derivada).

Es pot demostrar mitjançant un argument purament numèric i relativament senzill que hi ha llenguatges que no són generats per cap gramàtica. La demostració consisteix a mostrar que el conjunt de totes les gramàtiques sobre un determinat alfabet és numerable (atès que una gramàtica és una descripció finita), mentre que el conjunt de tots els possibles llenguatges sobre el mateix alfabet (igual que el conjunt potència de qualsevol conjunt infinit) és no numerable⁸.

1.2.1 La jerarquia de Chomsky

Es pot distingir entre quatre tipus de gramàtiques d’acord amb la forma de les productions.

tipus 0 o també gramàtiques estructurades per frases o gramàtiques sense restrictions. Les productions no tenen cap tipus de restricció additional.

tipus 1 o també gramàtiques sensibles al context o gramàtiques contextuals.Les produccions han de ser necessàriament de la forma

on x iy són cadenes de V*, β és una cadena de V+ i A és qualsevol símbol no terminal. El prefix x i el sufix y de la part esquerra (i dreta) de cada producció rep el nom de context.

tipus 2 o també gramàtiques de context lliure, gramàtiques independents del context o gramàtiques incontextuals9. Les produccions han de ser de la forma

A → a

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 s’haurien d’anomenar propiament gramàtiques regulars per la dreta. Es poden definir de la mateixa manera les gramàtiques regulars per l’esquerra exigint que les produccions siguen de la forma A →Ba en comptes de A →aB 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 d’un tipus n’hi ha una de l’altre 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 d’aquesta definició s’obtenen 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 d’una 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 d’aquestes noves produccions representa l’efecte 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ó d’una 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 n’afegeix una altra X → αγß.

La gramàtica resultant és equivalent, ja que les noves produccions reprodueixen l’efecte de les originals (que no desapareixen) juntament amb el de la producció .

Un cas particular d’aquest és l’eliminació 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 l’esquerra 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 l’altre 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 l’equivalència entre el llenguatge generat per una gramàtica i el llenguatge expressat mitjançant algun altre formalisme. El fet de demostrar rigorosament l’equivalència entre un llenguatge descrit formalment i una gramàtica s’anomena 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 l’equivalència entre aquestes i els corresponents llenguatges estarà suficientment clara.

Exemple 1.1 Demostrar que el llenguatge L format per les cadenes w ϵ {0,1}* que compleixen |w|₀ = 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

d’on 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|₀ = 2k + 1. Hi haurà dos casos:

1. w = lx i aleshores x compleix la hipótesi d’inducció i per tant

2. w = 0x. x tindrà un nombre parell de zeros i hi haurà dos subcasos:

(a) x = 1ⁱ es té que

(b) x = 1ⁱ 0y on y ha de contenir necessàriament 2l + 1 zeros i compleix la hipótesi d’inducció. 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 s’ha estudiat l’aspecte generatiu dels llenguatges es pot plantejar el problema contrari. És a dir, donada una cadena x qualsevol i una descripció (finita) d’un 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 s’anomenen 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 l’autòmat com aquell que està format per les cadenes que l’autòmat accepta.

Definirem al llarg d’aquest manual una família d’autò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 d’autòmats i les gramàtiques de la jerarquia de Chomsky. A més a més, s’estudiarà la relació entre el tipus de processament que pot fer l’autòmat més general i els límits del que es pot o no es pot computar des del punt de vista d’obtenció 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 d’un 1.

Exercici 1.9 Trobeu una gramàtica que genere cadenes en en les quals hi haja el doble de zeros que d’uns.

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

¹ No els nombres mateixos, sinó entesos com a símbols escrits en un paper, per exemple.

² 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

³ Fem notar que aquest conjunt és infinit.

⁴ En altres texts s’escriu també com a λ.

⁵ L’operació concatenació s’estén trivialment al cas de llenguatges definint

⁶ Com es fa en els diccionaris.

⁷ 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 d’elements de A. En aquest sentit també són homomorfismes les substitucions.

⁸ Aquesta demostració de no numerabilitat es dóna al final de l’apèndix A.

⁹ 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 s’oposa a incontextual i és, per tant, diferent de no contextual.