Escrito

UNIVERSIDAD POLITÉCNICA ESTATAL DEL CARCHI


FACULTAD DE INDUSTRIAS AGROPECUARIAS Y CIENCIAS AMBIENTALES
ESCUELA DE INFORMATICA
“Lenguajes y autómatas finitos”

AUTORES:
Bolaños Jiménez Steven Xavier
Ger Malquin Diego Mauricio
Pilamunga Cunalata Alex Javier
Villarreal García Byron Adair
ASESOR: Msc. Jeffery Naranjo
TULCÁN - ECUADOR
AÑO: 2015

Contenido
1. Lenguajes. Conceptos fundamentales3
2. Lenguajes y Expresiones Regulares 4
3. Autómata Finito 5
3.1. Minimización de Autómatas Finitos Deterministas 7
3.1.1. Explicación del algoritmo de Minimización 7
3.1.2. Ejemplo de Minimización de un Autómata Determinista 10
4. Teorema de equivalencia computacional 12
4.1. Teorema 1 12
4.2. Teorema 2 14
4.3. Teorema 3 14
Bibliografía 15

Figura 1 5
Figura 2 6
Figura 3 6
Figura 4 7
figura 5 8figura 6 9
figura 7 10
figura 8 11
figura 9 11
Figura 10 12
Figura 11 13
Figura 12 13
Figura 13 13
Figura 14 14









1. Lenguajes. Conceptos fundamentales
(Chacón, 2014)
“Sea Σ una colección finita de símbolos. Este conjunto de símbolos se denomina alfabeto y los elementos letras. Una palabra sobre Σ es una cadena de longitud finita de elementos de Σ. La cadena vacía o cadena nula, denotada porε, es una cadena que no contiene símbolos. El conjunto de todas las palabras sobre Σ se denota Σ ∗ . ε es una palabra en cualquier alfabeto Σ. Un lenguaje sobre Σ es un subconjunto de Σ ∗ . Si L denota el conjunto de los lenguajes sobre Σ se tiene que L = {L : L ⊂ Σ ∗}”
Note que ε, la cadena vacía, es la cadena que no contiene símbolos. Es diferente de ∅ el conjunto vacío (lenguaje vacío). Sesigue que {ε} es el conjunto que contiene exactamente una cadena, de hecho, la cadena vacía.
La longitud de una palabra u ∈ Σ ∗ , denotada por |u|, es el número de posiciones que tiene la palabra. Se puede definir recursivamente de esta manera:
|ε| = 0
|ua| = |u| + 1
donde u ∈ Σ ∗ y a ∈ Σ.
De este modo una palabra u ∈ Σ ∗ se puede definir por una función u : {1, 2, . . . , |u|} → Σ donde u(i) es laletra que se encuentra en la posición i en la palabra u.
Dos palabras u, v ∈ Σ ∗ son iguales si |u| = |v| y u(i) = v(i) para 1 ≤ i ≤ |u|.
Definimos una operación sobre Σ ∗ denominada concatenación. Para u, v ∈ Σ ∗ la concatenación de u y v se denota uv y se define a través de la función uv : {1, 2, . . . , |u| + |v|} → Σ

Así la palabra uv es la palabra que se obtiene escribiendo las letras deu y luego las letras de v. Si u = u1u2 · · · uk y v = v1v2 · · · vs entonces uv = u1u2 · · · ukv1v2 · · · v5 donde ui , vj ∈ Σ. Se deja al lector verificar que esta operación es asociativa.
Ejercicio 1
Pruebe que |uv| = |u| + |v|
Definición 1 Dados dos lenguajes L, M ∈ L, la concatenación de los lenguajes L y M se denota por LM y se define
LM = {vw : v ∈ L, w ∈ M}
Es fácil ver que laconcatenación de lenguajes es asociativa.
Ejemplo 1 Sean Σ = {0, 1} y L, M dos lenguajes sobre Σ dados por L = {1, 10} y M = {1, 01} entonces LM = {11, 101, 1001}. Mientras que ML = {11, 110, 001, 0110}.
Definición 2 Si Σ es un alfabeto y n ∈ N se define las potencias de Σ recursivamente de la siguiente manera:
1) Σ1 = Σ
2) Σn+1 = ΣΣn
Por convención se tiene que Σ 0 = {ε}.
2. Lenguajes y ExpresionesRegulares

(Chacón, 2014)

En aritmética, usamos las operaciones + y × para construir expresiones tales como
(4 + 1) × 5
De manera similar, usamos operaciones regulares para construir expresiones que describen lenguajes, las cuales se denominan expresiones regulares. Un ejemplo es:
(0 ∪ 1)0∗
El valor de la expresión aritmética es 25. El valor de una expresión regular es un lenguaje. En este caso ellenguaje consiste en todas las palabras que empiezan con 1 o 0 seguido por cualquier número (finito) de 0 s. Otro ejemplo de una expresión regular es
(0 ∪ 1)∗
Empieza con el lenguaje (0 ∪ 1) y se aplica la operación * . El valor de esta expresión son todas las palabras posibles de 0 s y 1s.

3. Autómata Finito
(De Castro, 2003)
Consideremos el lenguaje regular L representado por c ∗ (a∪bc∗ ) ∗ ....