• Author / Uploaded
• Graceziita Mantiilla

• Categories
• Matemáticas Aplicadas
• Áreas de informática
• Conceptos matemáticos
• Física y matemáticas
• Matemáticas

Citation preview

Facultad de Ciencias de la Ingeniería e Industrias Tema: Autómatas finitos Matemática Discreta

09/02/18 Patricio Aguirre 3er Semestre

Definición: Un autómata finito es un modelo matemático de una máquina que acepta cadenas de un lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estados y un conjunto de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. Sintaxis: Un autómata es una representación gráfica que muestra el proceso de reconocimiento de una cadena de entrada. La simbología utilizada es simple Cada nodo del grafo corresponde a un estado n, donde n es un número o bien una letra, generalmente. Una flecha de un estado a otro se denomina transición entre estados. El estado inicial se indica mediante una flecha. Los estados finales se representan con un círculo doble.

Clasificación Si para todo estado del autómata existe como máximo una transición definida para cada símbolo del alfabeto, se dice que el autómata es determinístico (AFD). Si a partir de algún estado y para el mismo símbolo de entrada, se definen dos o más transiciones se dice que el autómata es no determinístico (AFND). Formalmente un (AF) puede ser descrito como una 5-tupla A = (Q, Σ, δ, q0, F) donde:     

Q es un conjunto finito de estados Σ es un conjunto finito de símbolos o alfabeto. δ : Q × Σ -> Q es una función parcial llamada función de transición q0 ∈ Q estado inicial F ⊆ Q conjunto de estados finales.

Autómata determinístico: Los autómatas finitos son maquinas abstractas que procesan cadenas de entrada, las cuales son aceptadas o rechazadas: Si (u es aceptada). Cadena de entrada Autómata M“u” No (u no es aceptada). El autómata actúa leyendo los símbolos escritos sobre una cinta semi-infinita dividida en celdas o casillas, sobre la cual se escribe una cadena de entrada u, un símbolo por casilla. El autómata posee una unidad de control (cabeza lectora o unidad de memoria) que tiene un numero finito de configuraciones internas, llamados estados del autómata. Un autómata se define por los siguientes 5 componentes:     

Q Es un conjunto de estados; ∑ Es un alfabeto q0 ꜫ Q Es el estado inicial δ: Q x ∑ →QEs una función de transición F c Q Es un conjunto de estados finales o de aceptación.

Ejemplo: A = ({q0, q1, q2}, {a, b}, δ, q0, {q0, q1}) δ (q0, a)= q0 δ(q1, a)= q2 δ(q2, a)= q2 δ(q0, b)= q1 δ(q1, b)= q1 δ(q2, b)= q2

Autómata no determinístico: Un autómata finito no determinista (AFND) es un modelo matemático definido por la quíntupla M=(Q, ∑,f, q0, F) en el que:   



Q es un conjunto finito llamado conjunto de estados. ∑ es un conjunto finito de símbolos, llamado alfabeto de entrada. f es una aplicación llamada función de transición definida como: f: Q x (∑ U { λ}) → P(Q) donde P(Q) es el conjunto de las partes de Q, es decir, conjunto de todos los subconjuntos que se pueden formar con elementos de Q q0 es un elemento o estado de Q, llamado estado inicial.

 F es un subconjunto de Q, llamado conjunto de estados finales. Tabla de transición

Diagrama de Transición

Ejemplo: A = ({q0, q1, q2}, {a, b, c}, δ, q0, {q0, q1, q2}) δ (q0, a)= {q0, q1, q2} δ (q1, a)= ∅ δ (q2, a)= ∅ δ (q0, b)= {q1, q2} δ (q1, b)= {q1, q2} δ (q2, b)= ∅ δ (q0, c)= {q2} δ (q1, c)= {q2} δ (q2, c)= {q2}

Definición λ-clausura: 

Se llama λ-clausura de un estado al conjunto de estados a los que puede evolucionar sin consumir ninguna entrada, lo denotaremos como CL(q) o λclausura(q).  CL(q) se define recursivamente:  El estado q pertenece a la λ-clausura de q, qCL(q).  Si el estado pCL(q) y hay una transición del estado p al estado r etiquetada con una transición nula (λ), entonces r también está en CL(q).  Si PQ se llama λ-clausura de un conjunto de estados P a: CL(P)=  CL(q) qP  Algoritmo para el cálculo de λ-clausura(P) Procedimiento λ-clausura(P) Viejos= Nuevos=P Mientras viejosnuevos hacer Nuevos=viejos  {q / f(pi,λ)=q, piviejos} Fmientras λ-clausura(P)=nuevos Fin_procedimiento