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