automatas infinitos
Páginas: 2 (416 palabras)
Publicado: 2 de noviembre de 2014
Capítulo 2 Autómatas finitos
Un autómata finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguajeque el autómata reconoce. Los autómatas finitos tienen un conjunto de estados y su control pasa de un estado a otro en respuesta a las entradas externas.
Un autómata finito determinista es aquel quesólo puede estar en un único estado después
de leer cualquier secuencia de entradas. El término “determinista” hace referencia al hecho de que para cada entrada sólo existe uno y sólo un estado alque el autómata puede hacer la transición a partir de su estado actual.
Un autómata finito determinista consta de:
1. Un conjunto finito de estados, a menudo designado como Q.
2. Un conjunto finitode símbolos de entrada, a menudo designado como Σ.
3. Una función de transición que toma como argumentos un estado y un símbolo de entrada y devuelve un estado. La función de transición se designahabitualmente como δ.
4. Un estado inicial, uno de los estados de Q.
5. Un conjunto de estados finales o de aceptación F. El conjunto F es un subconjunto de Q.
El lenguaje de del AFD (AutómataFinito Determinista por sus siglas) es el conjunto de todas las cadenas que acepta. Una cadena es aceptada si, comenzando por el
estado inicial, la transición causada por el procesamiento de los símbolosde dicha cadena, uno cada vez, lleva a un estado de aceptación.
Comenzaremos con el AFD en el estado inicial, q0. Consultamos la función de transición δ , por ejemplo δ (q0,a1) = q1 para hallar elestado al que pasará el AFD A después de procesar el primer símbolo de entrada a1. A continuación procesamos el siguiente símbolo de entrada, a2, evaluando δ (q1,a2); supongamos que este estado es q2.Continuamos aplicando el mismo procedimiento para hallar los estados q3,q4, . . . ,qn tal que δ (qi−1,ai) = qi para todo i. Si qn pertenece a F, entonces la entrada a1a2 · · ·an se acepta y, si no...
Un autómata finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguajeque el autómata reconoce. Los autómatas finitos tienen un conjunto de estados y su control pasa de un estado a otro en respuesta a las entradas externas.
Un autómata finito determinista es aquel quesólo puede estar en un único estado después
de leer cualquier secuencia de entradas. El término “determinista” hace referencia al hecho de que para cada entrada sólo existe uno y sólo un estado alque el autómata puede hacer la transición a partir de su estado actual.
Un autómata finito determinista consta de:
1. Un conjunto finito de estados, a menudo designado como Q.
2. Un conjunto finitode símbolos de entrada, a menudo designado como Σ.
3. Una función de transición que toma como argumentos un estado y un símbolo de entrada y devuelve un estado. La función de transición se designahabitualmente como δ.
4. Un estado inicial, uno de los estados de Q.
5. Un conjunto de estados finales o de aceptación F. El conjunto F es un subconjunto de Q.
El lenguaje de del AFD (AutómataFinito Determinista por sus siglas) es el conjunto de todas las cadenas que acepta. Una cadena es aceptada si, comenzando por el
estado inicial, la transición causada por el procesamiento de los símbolosde dicha cadena, uno cada vez, lleva a un estado de aceptación.
Comenzaremos con el AFD en el estado inicial, q0. Consultamos la función de transición δ , por ejemplo δ (q0,a1) = q1 para hallar elestado al que pasará el AFD A después de procesar el primer símbolo de entrada a1. A continuación procesamos el siguiente símbolo de entrada, a2, evaluando δ (q1,a2); supongamos que este estado es q2.Continuamos aplicando el mismo procedimiento para hallar los estados q3,q4, . . . ,qn tal que δ (qi−1,ai) = qi para todo i. Si qn pertenece a F, entonces la entrada a1a2 · · ·an se acepta y, si no...
Leer documento completo
Regístrate para leer el documento completo.