Burjassot, 25 de juny de 2004
SÍMBOLS UTILITZATS
Relació binària dequivalència. Classe dequivalència de R que conté lelement a. Conjunt quocient del conjunt A induït per la relació R. Conjunt potència de A o conjunt parts de A. Ø Conjunt buit, llenguatge buit. ɛ Cadena buida. Símbol blanc. {ɛ} Llenguatge format per la cadena buida. Nombres enters: 0, 1, 2,. .. Congruència associada a un llenguatge L. Congruència associada a un autòmat A. Alfabets o vocacularis. Monoide lliure sobre X. Quocient (per la dreta) del llenguatge L1 pel llenguatge L2. a, b, c,... Símbols terminals (en gramàtiques). X, Y, Z,... Símbols no terminals. x, y, z,... Cadenes de símbols no terminals. u, v, w,... Cadenes de símbols terminals. α, β,... Cadenes de símbols de qualsevol tipus. q, P Tancament èpsilon dun estat o dun conjunt destats. xR Inversió o reflexió de la cadena x. α β Producció. Derivació directa. Tancament i tancament transitiu de =K Implicació lògica. δ Funció de transició. Moviment. Computació (tancament transitiu de 1). n-equivalència i equivalència entre estats. Reducció entre problemes. Reducció polinòmica entre problemes. Codificació (efectiva) de x.1. Llenguatges formals i computació
Aquest manual té com a objectiu lestudi dels llenguatges formals, així com dels seus generadors i acceptors, juntament amb lestreta 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 shi 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 lapèndix A sofereix 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 enters1 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 dun alfabet determinat.
Per exemple, aaabbba, 1024 i 2, 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 duna cadena x com a |x|.
Estendrem la notació per referirnos al nombre de símbols dun 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 alfabet3, podem definir certes operacions internes dins daquest, 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 lesquerra 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. Lelement neutre daquest conjunt respecte de la concatenacio (que ho és per lesquerra 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 manual4 com a ε.
Diem que una cadena y és prefix duna altra cadena x si i només si existeix alguna cadena z tal que x = yz.
Diem que una cadena y és sufix duna 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) duna 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 dun 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 dexpressar el primer daquests 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 sescriuen 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 llenguatges5, 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, shi suposa donada una relació dordre total que origina el que sanomena ordenació alfabètica. A partir daquesta 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 duna mateixa longitud, ordenar-les per ordre alfabètic6.
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 duna cadena x com la concatenació de x amb ella mateixa i vegades. Sescriu
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ó duna 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