Teoria De La Computacion..Afd(Afnd),Etc.

INSTITUTO TECNOLÓGICO SUPERIOR P´URHEPECHA.

CARRERA: INGENIERÍA EN SISTEMAS COMPUTACIONALES.

NOMBRE DE LA MATERIA: TEORÍA DE LA COMPUTACIÓN.

Temas: UNIDAD II.
2.1 Autómatas finitos
2.1.1 Autómatas finitos determinísticos.
2.1.2 Autómatas finitos No determinísticos.
2.2 Expresiones regulares.
2.3 Lenguajes no regulares.

1.- Desarrollar ejercicios para la representación delenguajes por medio de AFD, AFN, AFN-y expresiones regulares.
2.- Investigar que otras aplicaciones tiene la teoría de lenguajes regulares.
INTRODUCCIÓN:

AUTÓMATA FINITO DETERMINÍSTICO (AFD):
Es un modelo matemático que consiste de:
* Un conjunto de estados, denominado S.
* Un conjunto (alfabeto) de símbolos de entrada, denominado ∑.
* Una función de transición move que mapea un parP ( s , a ) a un estado t.
s y t son estados contenidos en S, a es un símbolo de entrada.
* Un estado de inicio, denotado por s0.
* Un conjunto de estados de aceptación (finales), denotado por F.
Además, un autómata finito determinístico AFD debe cumplir con las siguientes
características:
a) No hay transiciones etiquetadas por ɛ.
b) Para cada estado s y un símbolo de entrada a,existe a lo más un arco etiquetado por a saliendo de s.

AUTÓMATA FINITO NO DETERMINÍSTICO (AFND):
Un autómata finito no determinista (abreviado AFND) es un autómata finito que, a diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.
En un AFND puede darse cualquiera deestos dos casos:
* Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
* Que existan transiciones del tipo δ(q,ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.
Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estastransiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada. Considérese una modificación al modelo del autómata finito para permitirle ninguna, una o más transiciones de un estado sobre el mismo símbolo de entrada.

AUTÓMATA FINITO NO DETERMINISTA CON TRANSICIONES Ε (AFND-ɛ):
Propiedades.-
Para todo , se escribe si y solo si a q se pude llegar desde p, yendo alo largo de cero o más flechas ε. En otras palabras, si y sólo si existe donde tal que
.
Para cualquier, el conjunto de estados que se puede llegar a partir de p se llama epsilon-closure o ε-closure de p y se escribe como
.
Para cualquier subconjunto, definir el ε-closure de P como
.
Las transiciones epsilon son transitive, ya que puede demostrarse que para todo y , si y , entonces .
Delmismo modo, si y entonces Sea x una cadena del alfabeto Σ∪{ε}. Un AFND-ε M acepta la cadena x si existe tanto una representación de x de la forma x1x2 ... xn, donde xi ∈ (Σ ∪{ε}), y una secuencia de estados
p0,p1, ..., pn, donde pi ∈ Q, Cumpliéndose las siguientes condiciones:
1. p0 E({q0})
2. pi E(T(pi-1, xi )) para i = 1, ..., n
3. pn F.

EXPRESIONES REGULARES:
Expresiones regularesSe denominan expresiones regulares sobre un alfabeto A, a las expresiones que se pueden construir a partir de las siguientes reglas:
Ф es una expresión regular que describe el lenguaje vacío;
ɛ es una expresión regular que describe el lenguaje {ɛ}, esto es el lenguaje que contiene únicamente la cadena vacía;
- Para cada símbolo a ∑ A, a es una expresión regular que describe el lenguaje {a},esto es el lenguaje que contiene únicamente la cadena a;
- Si r y s son expresiones regulares que describen los lenguajes L(r) y L(s) respectivamente:
i) r + s es una expresión regular que describe el lenguaje L(r) L(s)
ii) r . s es una expresión regular que describe el lenguaje L(r) . L(s)
iii) r* es una expresión regular que describe el lenguaje L(r)*.
El operador de clausura es el que...