Buch lesen: "Teoria d'autòmats i llenguatges formals"

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