Lenguaje Y Automatas

Lenguajes & Autómatas

Alfabeto

La noción más primitiva es la de símbolo, que es simplemente una representación distinguible de cualquier información.

Los símbolos pueden ser cualesquiera, como w, 9, #, etc., pero nosotros vamos a utilizar las letras a,b,c, etc. Un símbolo es una entidad indivisible

Un alfabeto es un conjunto finito no vacío de símbolos, En general utilizaremos la notación Σ para representar un alfabeto.

También se puede definir las tablas ASCII y EBCDIC como los alfabetos de distintos ordenadores.

Cadenas

Con los símbolos de un alfabeto es posible formar secuencias o cadenas de caracteres, tales como mxzxptlk, balks , r , etc.

Las cadenas de caracteres son llamadas también palabras, la longitud o tamaño de una cadena w es el número de elementos que contiene la cadena.

Cadena vacía

Existe una cadena denominada cadena vacía, que no tiene símbolos y se denota con, entonces su longitud es: 0

Concatenación

La concatenación de dos cadenas u y v, escrita uv, es “pegar” las dos cadenas para formar una nueva.

Ejemplo: Sea u=ab , v=ca y w=bb. Entonces

uv=abca vw=cabb

(uv)w=abcabb u(vw)=abcabb

El resultado de la concatenación de u,v y w es independiente de el orden en que las operaciones son ejecutadas.

Potencias de un alfabeto

Observe que Σ0={ε}, independientemente de cuál sea el alfabeto Σ. Es decir, ε es la única cadena cuya longitudes 0.

Si Σ={0,1}, entonces Σ1={0,1}, Σ2={00,01,10,11} ,Σ3={000,001,010,011,100,101,110,111}

Observe que existe una ligera confusión entre Σ y Σ1. Lo primero es un alfabeto; sus elementos 0 y 1 son los símbolos. Lo segundo es un conjunto de cadenas; sus elementos son las cadenas 0 y 1, cuya longitud es igual a 1. No vamos a utilizar notaciones diferentes para los dos conjuntos, confiando en que el contexto deje claro si {0,1} o algún otro conjunto similar representa un alfabeto o un conjunto de cadenas.

Lenguaje

Un conjunto de cadenas, todas ellas seleccionadas de un Σ∗, donde Σ es un determinado alfabeto se denomina lenguaje.

Si Σ es un alfabeto y L ⊆ Σ∗, entonces L es un lenguaje de Σ.

Observe que un lenguaje de Σ no necesita incluir cadenas con todos los símbolos de Σ, ya que una vez que hemos establecido que L es un lenguaje de Σ, también sabemos que es un lenguaje de cualquier alfabeto que sea un super conjunto de Σ.

Representación finita del lenguaje

Un lenguaje consiste de un grupo de cadenas de un alfabeto. Usualmente ciertas restricciones se aplican a las cadenas del lenguaje. Por ejemplo el lenguaje Español consiste de todas las cadenas de palabras que nosotros llamamos oraciones.

No todas las combinaciones de palabras forman oraciones. De allí que un lenguaje

...