LENGUAJES Y AUTÓMATAS 1 Alfabeto, Cadenas y Lenguajes

Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
Rocket clouds
LENGUAJES Y AUTÓMATAS 1 Alfabeto, Cadenas y Lenguajes por Mind Map: LENGUAJES Y AUTÓMATAS 1 Alfabeto, Cadenas y Lenguajes

1. Alfabetos

1.1. Es un conjunto finito A. Sus elementos se llamaran símbolos o letras.

1.2. Ejemplo 1 Binario: A={0,1} es un alfabeto con símbolo 0 y 1.

1.3. Ejemplo 2 Binario: B={<0,0>,<0,1>,<1,0>,<1,1>} con simbolos <0,0>,<0,1>,<1,0>,<1,1> en este caso no hay que confundir los simb

1.4. Ejemplo 3 letras minúsculas: ∑={a, b, ..., z}

2. Cadenas

2.1. Una cadena de un conjunto X es una secuencia finita de elementos de X. Las cadenas son objetos fundamentales usados en la definición de lenguajes.

2.2. Ejemplo 1: 01101 es una cadena del alfabeto binario.

2.3. Ejemplo 2: Sea X={a,b,c}. Las siguientes son cadenas de ese alfabeto: abc, ccb, cab, aaaa, bbb, ccc.

2.4. Tipos de Cadenas.

2.4.1. Cadena de caracteres:que también se denomina en ocasiones palabra, es una secuencia finita de símbolos seleccionados de algún alfabeto.

2.4.2. Cadena vacía: Es aquella cadena que representa cero apariciones de símbolos. Esta cadena, esta designada por ɛ , | ɛ |= 0, es una cadena que puede construirse en cualquier alfabeto.

2.5. Longitud de una cadena.

2.5.1. Es el numero de posiciones ocupada por símbolos dentro de la cadena, por ejemplo 01101 tiene una longitud de cinco. Es habitual decir que la longitud de una cadena es igual al numero de símbolos que contiene.

3. Subcadenas

3.1. Decimos que una cadena z es subcadena de otra cadena ω si existen cadenas x, y ϵ ∑*  tal que ω = x · z · y

3.2. Prefijo(ω) = {x ϵ ∑*  | Ǝ z ϵ ∑*  : ω = x · z}

3.2.1. Un prefijo de una cadena x es una subcadena inicial de x, es decir una cadena y es un prefijo si existe una cadena z tal que x = yz y de manera similar z es un sufijo de x.

3.2.2. Los prefijos propios son aquellas cadenas que son prefijos de una palabra pero no iguales a la misma.

3.2.2.1. Un prefijo y de x es un prefijo propio de x si y≠ϵ  y y≠x

3.3. Sufijo(ω) = {x ϵ ∑*  | Ǝ z ϵ ∑*  : ω = z · x}

3.3.1. Un sufijo z de x es un sufijo propio de x si z≠ϵ  y z≠x

4. Lenguajes

4.1. Un conjunto de cadenas, todas ellas seleccionadas de un ∑*, donde ∑ es un determinado alfabeto, se denomina lenguaje.

4.1.1. Ejemplo

4.1.1.1. El lenguaje L de cadenas del alfabeto {a,b} en donde cada cadena comienza con una a y tiene longitud par. Las cadenas aa, ab, aaaa, abbb, abab, abbbaaba, forman parte de ese lenguaje.

4.2. Los lenguajes habitualmente pueden interpretarse como conjuntos de cadenas. Un ejemplo seria el ingles donde la colección de las palabras correctas inglesas es un conjunto de cadenas del alfabeto que consta de todas las letras.

4.3. El lenguaje español consiste que todas la cadenas de palabras que nosotros llamamos oraciones. no todas las combinaciones de palabras forman oraciones.

4.4. Un lenguaje consiste de un subconjunto de el conjunto de todas las posibles cadenas que pueden formar del alfabeto.

5. Compilador (Traductor)

5.1. Caracteristicas

5.1.1. El programa se compila una sola vez, pero se puede ejecutar muchas.

5.1.2. La ejecución del programa objeto es mucho más rápida que la interpretación del fuente.

5.1.3. El compilador tiene una visión completa del programa, por lo que puede dar una información más detallada de los errores cometidos por el programador.

5.2. fases

5.2.1. .

6. Traductores

6.1. Caracteristicas

6.1.1. El traductor necesita menos memoria que el compilador.

6.1.2. Permite una mayor interactividad con el código en tiempo de desarrollo.

7. Citas bibliograficas

7.1. (Elena Jurado Málaga, 2008)

7.2. (Johon E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, 2007)

7.3. (Domingo Gómez & Luis M. Pardo, 2012)

7.4. Dr. Ramon Zatarain Cabada, 2009