Unidad 2 teoría de la computación

UNIDAD II: LENGUAJES REGULARES AUTOMATAS FINITOS 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. El autómata finito acepta una cadena x si la secuencia de transicionescorrespondientes a los símbolos de x conduce desde el estado inicial a un estado final. 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 unautómata finito se define como una 5-upla M = donde E: conjunto finito de estados A: alfabeto o conjunto finito de símbolos de entrada d: función de transición de estados, que se define como - d: E x A ® E si el autómata es determinístico - d: E x A ® P(E) si el autómata es no determinístico (P(E) es el conjunto potencia de E, es decir el conjunto de todos los subconjuntos de E) e0: estadoinicial; e0 Î E F: conjunto de estados finales o estados de aceptación; F Í E Generalmente se asocia con cada autómata un grafo dirigido, llamado diagrama de transición de estados. Cada nodo del grafo corresponde a un estado. El estado inicial se indica mediante una flecha que no tiene nodo origen. Los estados finales se representan con un círculo doble. Si existe una transición del estado ei al estadoej para un símbolo de entrada a, existe entonces un arco rotulado a desde el nodo ei al nodo ej; es decir que d(ei, a) = ej, se representa en el diagrama.

2.1.1 AUTÓMATAS FINITOS DETERMINÍSTICOS (DFA’S). Las características de los autómatas finitos determinísticos son: 1. Un conjunto finito de estados y un conjunto de transiciones de estado a estado, que se dan sobre símbolos de entrada tomadosde un alfabeto Σ. 2. Para cada símbolo de entrada existe exactamente una transición a partir de cada estado (posiblemente de regreso al mismo estado). 3. Un estado, por lo general denotado como q0 es el estado inicial, en el que el autómata comienza.

4. Algunos estados (tal vez ninguno) están designados como final o de aceptación. Un autómata finito determinístico es una quinta tupla (Q, Σ,δ, q0, F) donde: Q es un conjunto finito de estados. Σ un alfabeto de entrada finito. q0 elemento de Q , el estado inicial. F⊆ Q el conjunto de estados finales o de aceptación. δ es la función δ : Q x Σ → Q que determina el único estado siguiente para el par (q1, ζ) correspondiente al estado actual q1 y la entrada ζ. Generalmente el término autómata finito determinístico se abrevia como DFA de sussiglas en inglés Deterministic Finite Automaton. Usaremos M = (Q, Σ, q0, F, δ) para indicar el conjunto de estados, el alfabeto, el estado inicial, el conjunto de estados finales y la función asociadas con el DFA M. Se puede construir un diagrama para que ayude a determinar los distintos miembros o cadenas del lenguaje. Tal diagrama tiene la forma de un grafo dirigido con información añadida, y sellama diagrama de transición. Los nodos del grafo corresponden a los estados del DFA y se usan para señalar, en ese momento, hasta qué lugar se analizó la cadena. Por lo general q0 es el estado inicial, marcando con una flecha (→), el comienzo del autómata; algunos estados están designados como final o aceptación indicados por un doble círculo. Los símbolos del alfabeto son las etiquetas de losarcos del grafo. Si cuando ha sido tratada la cadena en su totalidad se termina en un estado de aceptación entonces la cadena es aceptada por el lenguaje. Si M es un AFD, entonces el lenguaje aceptado por M es L(M)={w ∈ Σ*⏐ es aceptada por M}. Por tanto, L(M) es el conjunto de cadenas w que hacen que M pase de su estado inicial a un estado de aceptación. Ejemplo: El lenguaje que acepta el DFA...