PORTADA

UNIVERSIDAD AUTÓNOMA DEL ESTADO DE MÉXICO

CENTRO UNIVERSITARIO UAEM ATLACOMULCO

LICENCIATURA EN INGENIERÍA EN COMPUTACIÓN

MATERIA: 

AUTÓMATAS Y LENGUAJES FORMALES.

ALUMNO: 

JUAN CARLOS CELESTINO GUILLERMO

DOCENTE: 

ING. HECTOR CABALLERO HERNÁNDEZ

"Lista De Trabajos"

Lista De Trabajos

Listas

1. Lista de Programas.

2. Lista de Resúmenes e Investigaciones.

3. Firmas.

FIRMAS

RESUMEN

INVESTIGACIONES Y RESÚMENES

1. Gramática Generativa De Chomsky.
2. Operaciones Con Conjuntos.
3. Manejo De Excepciones y Clase String.
3. Tesis Para Maestría: "Reconocedor De Lenguajes Con Base En Gramáticas Formales". Horacio Arberto García Salas.

2. Operaciones Con Conjuntos.

RESUMEN.

“AUTOMATA FINITO NO DETERMINISTA”

QUINTUPLA:

Qà Conjunto finito de nodo.

∑à  Alfabeto finito.

q₀à Estado inicial.

F à Estado final.

dà Función de transición de   Estado (Cadena).

QUINTUPLA DEL AUTOMATA:

Q = {q₀, q₁, q₂, q₃, q₄}

∑ = {0,1}.

q₀ = {q₀}.

F = {q₂,q₄}. 

EJERCICIO DE CADENA:

M = 01001

d(q₀, 0)= {q₀, q₃}.

d(q₀, 01)= d(d(q₀, 0), 1)= d({q₀, q₁}, 1)= d({q₀, q₃})= d(q₀, 1)È d(q₃, 1)= {q₀, q₁}.

d(q₀, 010)= {q₀, q₃}, d(q₀, 0100)= {q₀, q₃, q₄}.

d(q₀, 01001)= {q₀, q₁, q₂}.

  

M=1000111

·         d(q₀, 1)= {q₀, q₁}.

·         d(q₀, 10)= {q₀, q₃}, d(q₁, 10)= {ERROR} à d({q₀, q₁}, 10)= {q₀, q₃}.

·         d(q₀, 100)= {q₀, q₃}, d(q₃, 100)= {q₄} à d({q₀, q₃}, 100)= {q₀, q₃, q₄}.

·         d(q₀, 1000)= {q₀, q₃}, d(q₃, 1000)= {q₄}, d(q₄, 1000)= {q₄}

                 à d({q₀, q₃, q₄}, 1000)= {q₀, q₃, q₄}.

·         d(q₀, 10001)= {q₀, q₁}, d(q₃, 10001)= {ERROR}, d(q₄, 10001)= {q₄}

                 à d({q₀, q₃, q₄}, 10001)= {q₀, q₁, q₄}.

·         d(q₀, 100011)= {q₀, q₁}, d(q1, 100011)= {q₂}, d(q₄, 100011)= {q₄}

                à d({q₀, q₁, q₄}, 100011)= {q₀, q₁, q₂, q₄}.

·         d(q₀, 1000111)= {q₀, q₁}, d(q₁, 1000111)= {q₂}, d(q₂, 1000111)= {q₂},          d(q₄, 1000111)= {q₄} à d({q₀, q₁, q₂, q₄}, 1000111)= {q₀, q₁, q₂, q₄}.

M=1111000

·      d(q₀, 1)= {q₀, q₁}.

·      d(q₀, 11)= {q₀, q₁}, d(q₁, 11)= {q₂},

           à d({q₀, q₁}, 11)= {q₀, q₁, q₂}.

·      d(q₀, 111)= {q₀, q₁}, d(q₁, 111)= {q₂}, d(q₂, 111)= {q₂},

                à d({q₀, q₁, q₂}, 111)= {q₀, q₁, q₂}.

·      d(q₀, 1111)= {q₀, q₁}, d(q₁, 1111)= {q₂}, d(q₂, 1111)= {q₂},

               àd({q₀, q₁, q₂}, 1111)= {q₀, q₁, q₁}.

·      d(q₀, 11110)= {q₀, q₃}, d(q₁, 11110)= {ERROR}, d(q₂, 11110)= {q₂}=

               àd({q₀, q₁, q₂}, 11110)= {q₀, q₂, q₃}.

·      d({q₀, q₂, q₃}, 111100)= {q₀, q₂, q₃, q₄}.t

·      d({q₀, q₂, q₃, q₄}, 1111000)= {q₀, q₂, q₃, q₄}.

“OPERACIONES CON CONJUNTOS.”

UNION

La unión de dos conjuntos A y B la denotaremos por A  B y es el conjunto  formado por los elementos que pertenecen al menos a uno de ellos ó a los dos. Lo que se denota por:

A È B = { x/x € A ó x € B }

INTERSECCION

Sean A= { 1, 2, 3, 4, 5, 6, 8, 9 } y B={ 2, 4, 8, 12 }

Los elementos comunes a los dos conjuntos son: { 2, 4, 8 }. A este conjunto se le llama intersección de A y B; y se denota por A  B, algebraicamente se escribe así:

A Ç B = {x/x € A y x € B }

Y se lee el conjunto de elementos x que están en A y están en B.

CONJUNTO VACIO

Un conjunto que no tiene elementos es llamado conjunto vacío ó conjunto nulo lo que denotamos por el símbolo Æ .

  

CONJUNTOS AJENOS

Sí la intersección de dos conjuntos es igual al conjunto vacío, entonces a estos conjuntos les llamaremos conjuntos ajenos, es decir:

Si A Ç B = Æ entonces A y B son ajenos.

COMPLEMENTO

El complemento de un conjunto respecto al universo U es el conjunto de elementos de U que no pertenecen a A y se denota como A' y que se representa por comprensión como:

A'= {x € U/x y x € A }

DIFERENCIA

Sean A y B dos conjuntos. La diferencia de A y B se denota por A-B y es el conjunto de los elementos de A que no están en B y se representa por comprensión como:

A - B= { x/x € A ; X € B }

DIAGRAMAS DE VENN

Los diagramas de Venn que deben al filósofo inglés John Venn (1834-1883) sirven para encontrar relaciones entre conjuntos de manera gráfica mediante dibujos ó diagramas.

La manera de representar el conjunto Universal es un rectángulo, ó bien la hoja de papel con que se trabaje.

Un ejemplo de la representación del conjunto universal se muestra como: 

EJEMPLOS DE OPERACIONES CON CONJUNTOS

1. Consideremos el conjunto universo como U={x / x es un número dígito}, o lo que es equivalente a decir que U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Y tomemos dos subconjuntos de nuestro universo, los cuales serán:

·         A={x / x es un número dígito primo}, o equivalente a A={2, 3, 5, 7} 

·         B={x / x  es un número dígito par}, o equivalente a B={2, 4, 6, 8}.

Encontrar la unión, intersección, diferencia y complemento entre A y B. 

“NOTACIONES DE EXPRESIONES REGULARES.”

La notación de conjuntos nos permite describir los lenguajes regulares, pero nosotros quiso éramos una notación en que las representaciones de los lenguajes fueran simplemente texto (cadenas de caracteres). Así las representaciones de los lenguajes regulares serian simplemente palabras de un lenguaje (el de las representaciones correctamente formadas).

Con estas ideas vamos a venir un lenguaje, el de las expresiones regulares, en que cada palabra va a denotar un lenguaje regular.

Definición.- Sea Σ un alfabeto. El conjunto ER de las expresiones regulares sobre Σ contiene las cadenas en el alfabeto Σ∪{“∧”, “+”, “•”, “∗”, “(”, “)”, “Φ”} que cumplen con lo siguiente:

1.    “∧” y “Φ” ∈ ER

2.    Si σ ∈ Σ, entonces σ ∈ ER.

3.    Si E1,E2 ∈ ER, entonces “(”E1“+”E2“)” ∈ ER, “(”E1“•”E2“)” ∈ ER, “(”E1“)∗” ∈ ER.

Las comillas “ ” enfatizan el hecho de que estamos definiendo cadenas de texto, no expresiones matemáticas 3. Es la misma diferencia que hay entre el carácter ASCII “0”, que se puede teclear en una terminal, y el número 0, que sínica que se cuenta un conjunto sin ningún elemento.

Ejemplos.- Son ER en {a,b,c} las siguientes: “a”, “((a+b))∗”, “((a•b)•c)”. No son ER:“ ab”, “((a•b(c)∗)”.

Significado de las ER

Las ER son simplemente fórmulas cuyo propósito es representar cada una de ellas un lenguaje. Así, el significado de una ER es simplemente el lenguaje que ella representa. Por ejemplo, la ER “Φ” representa el conjunto vacío {}. Para comprender intuitivamente la manera en que las ER representan lenguajes, consideremos el proceso de verificar si una palabra dada w pertenece o no al lenguaje representado por una ER dada. Vamos a decir que una palabra “empata” con una expresión regular si es parte del lenguaje que esta representa.

La palabra vacía ε “empata” con la ER ∧. 3Este último es el caso de las expresiones de conjuntos para describir los conjuntos regulares.

EXPRESIONES REGULARES Y GRAMATICAS REGULARES

Una palabra de una letra como “a” empata con una ER consistente en la misma letra “a”, “b” empata “b”, etc.

Luego, una palabra w = uv, esto es w está formada de dos pedazos u y v, empata con una expresión (U •V ) a condición de que u empate con U y v empate con V .

Por ejemplo, abc empata con (a•(b•c)) porque abc puede ser dividida en a y bc, y a empata con a en la ER, mientras que bc empata con (b•c) separando b y c de la misma manera. Similarmente, cuando la ER es de la forma (U + V ), puede empatar con una palabra w cuando esta empata con U o bien cuando empata con V .

Por ejemplo, bc empata (a+(b•c)). Una palabra w empata con una expresión U∗ cuando w puede ser partida en pedazos w = w1w2,... de tal manera que cada pedazo wi empata con U. Por ejemplo, caba empata con (((c + b) • a))∗ porque puede partirse en los pedazos ca y ba, y ambos empatan con ((c + b)•a), lo cual es fácil de verificar. A continuación definiremos formalmente la correspondencia entre la representación (una ER) y el lenguaje representado.

Definición.- El significado de una ER es una función L : ER →2Σ∗ (esto es, una función que toma como entrada una expresión regular y entrega como salida un lenguaje), definida de la manera siguiente:

1.    L(“Φ”) = ∅ (el conjunto vacío)

2.    L(“∧”) = {ε}

3.    L(“σ”) = {σ},σ ∈ Σ.

4.    L(“(”R“•”S“)” ) = L(R)L(S),R,S ∈ ER

5.    L( “(”R“+”S“)” ) = L(R)∪L(S),R,S ∈ ER

6.    L( “(”R“)∗” ) = L(R)∗,R ∈ ER

Para calcular el significado de una ER en particular, se aplica a ella la función L. Las ecuaciones dadas arriba se aplican repetidamente, hasta que el símbolo L desaparezca.

Ejemplo.- El significado de la ER “(((a + b))∗•a)” se calcula de la manera siguiente:

·     L(“(((a + b))∗•a)”) = L(“((a + b))∗”)L(“a”) -usando 4, = L(“(a + b)”)∗{a} -por 6 y 3, = (L(“a”) ∪L(“b”))∗{a} -aplicando 5, = ({a}∪{b})∗{a} = {a}∗{a} -usando 3 y simplificando.

EXPRESIONES REGULARES

Este es el lenguaje de las palabras sobre {a,b} que terminan en a. Con objeto de hacer la notación menos pesada, vamos a simplificar las ER de la manera siguiente:

1.    Omitiremos las comillas “ ”.

2.    Se eliminan los paréntesis innecesarios.

3.    Se supone una precedencia de operadores en el orden siguiente: primero “∗”, luego “•” y finalmente “+”. Además se supone que los operadores “•” y “+” son asociativos.

4.    Eventualmente omitiremos el operador “•”, suponiendo que ´este se encuentra implícito entre dos subexpresiones contiguas.

Ejemplos.- a, (a + b)∗, abc, ac∗ son tomados como “a”, “((a + b))∗”, “((a • b) • c)” y“( a•(c)∗)”, respectivamente.

Ejemplo.- Encontrar una expresión regular para el lenguaje en {a,b}∗ en el que inmediatamente antes de toda b aparece una a.

Solución.- Una posible ER es (a + ab) ∗

Una solución aceptable para este tipo de problemas debe cumplir dos características:

1.    Corrección.- Las palabras que represente la ER propuesta deben satisfacer la descripción del problema (por ejemplo, para el problema del ejemplo, la solución a∗(a + b)∗ no es adecuada porque representa algunas palabras, como abb, que no satisfacen la condición de que toda b esté inmediatamente precedida por una a.

2.  Completez.- La ER propuesta debe representar todas las palabras que satisfagan la condición. Así, para el problema del ejemplo, la solución (ab)∗ no es adecuada porque hay palabras tales como aab, pertenecientes al lenguaje, que no son representadas por dicha ER.