Teoría De Autómatas Y Lenguajes Formales

ELEMENTOS BÁSICOS: ALFABETOS, PALABRAS Y LENGUAJES

 Alfabeto: Conjunto finito y no vacío cuyos elementos se denominan símbolos. Para designarlo se utilizan letras mayúsculas del alfabeto griego, especialmente Σ y Γ. Como ejemplos de alfabetos, contamos con {0,1} alfabeto binario; {a,b,c…x,y,z} alfabeto latino de letras minúsculas…

 Palabras: Secuencia finita de símbolos de un alfabeto, cuando además queremos dejar claro que los símbolos que se utilizan son los de un alfabeto determinado, se habla de palabras sobre un alfabeto. Por ejemplo, según el alfabeto {a,b} son palabras de este alfabeto aba, aab, aaabbaaaa, a, b y λ (ésta última es una secuencia vacía de símbolos y representa la palabra vacía, por lo cual es una palabra sobre cualquier alfabeto).

 Subpalabras, prefijos y sufijos: Las subsecuencias de símbolos consecutivos de una palabra reciben el nombre de subpalabras de esta palabra. Se consideran subpalabras impropias la palabra vacía y la entera y el resto se consideran propias. Por ejemplo los prefijos de la palabra bbaab son {λ, b bb, bba, bbaa, bbaab} de los cuales el primero y el último son prefijos impropios y el resto propios.

 Lenguajes, conjunto de palabras: Un lenguaje es un conjunto de palabras sobre un alfabeto determinado, para designarlos se usa la letra L con subíndices si es necesario, y otras letras mayúsculas del alfabeto latino. Algunos ejemplos de lenguajes sobre el alfabeto {a,b} son L1={a, aa, aaa}; L2= {a, b, aa, bb, ab, abababab}; L3={λ}. No obstante, un lenguaje no debe ser necesariamente finito, por ejemplo, lenguaje de todas las palabras sobre Σ={0,1} que comiencen por el símbolo 1.

OPERACIONES SOBRE PALABRAS

 Concatenación: Concatenar dos palabras significa construir una palabra nueva añadiendo los símbolos de la segunda tras los símbolos de la primera, el operador de concatenación es el símbolo ·. Así aaa·bbb=aaabbbb, aba· λ=aba. La concatenación no es conmutativa, porque en general w1·w2<>w2·w1; sí tiene en cambio la propiedad asociativa y la palabra vacía λ constituye el elemento neutro de la concatenación. La concatenación de una palabra consigo misma se suele representar con notación exponencial, de manera que w2=w·w; y la concatenación de una palabra y un símbolo se denota de la misma manera que la concatenación de dos palabras.

 Longitud: el número de símbolos de una palabra se desgina por |w| y es interesante reconocer que: |w1·w2|=|w1|+|w2| y |w|=0  w= λ.

 Número de ocurrencias de un símbolo: la notación |w|a denota el número de apariciones del símbolo a en la palabra w, así |aabbabaa| a = 5.

 Inversión: Consiste en escribir al revés una palabra dada, la palabra resultante de la inversión se denomina inversa, si w es una palabra cualquiera wR denota su inversa; así (ab)R=ba, (011101) R=101110, λ R= λ. Fijémonos que (w1·w2) R =(w2) R·(w1)

...