Aut Matas Finitos No Determinista
Páginas: 2 (489 palabras)
Publicado: 20 de marzo de 2015
Autómatas finitos no determinista:
Un Autómata Finito No Determinista (AFN) se define como una quíntupla de la siguiente manera:
A= (Q, T, λ, q0, F) donde:
Q = Conjunto finito y no vacío deestados,
T = Alfabeto de entrada,
λ = Función de transición que toma como argumentos un estado de Q y un símbolo de T, y devuelve un subconjunto de estados de Q.
q0 = Subconjunto de Q que representa alconjunto de estados iniciales (a diferencia de los AFD, los AFN pueden admitir varios estados iniciales).
F = Subconjunto de Q que representa al conjunto de estados de aceptación (estados finales).Los Autómatas Finitos No Deterministas, también llamados AFN, se caracterizan porque, a diferencia de los AFD, en un estado puede haber más de una transición posible para un mismo símbolo de entrada(alfabeto). Es decir /λ(a)/ ≥ 1 para algún "q" perteneciente a Q y para algún símbolo "a" perteneciente a T.
Ejemplo : Según el siguiente autómata :
Donde λ(q0,01)=λ(λ(q0,0),1)=λ({q0,q1},1)={q0,q1}.
Otra diferencia importante de los AFN con respecto a los AFD es la posibilidad de tener más de un estado inicial.
El lenguaje aceptado por un AFN es el conjunto de cadenas tales que después deser analizadas, el AFN ha logrado alcanzar al menos un estado de aceptación. Tales lenguajes de definen de la siguiente manera:
L(A) = {x perteneciente a T*/ λ (q0, x) intersección F≠ Ø}.
Esimportante establecer que para un lenguaje L aceptado por un AFN, entonces existe un AFD que también acepta el lenguaje L. Es por esto que se hace posible, a partir de un AFN diseñar un AFD equivalente.
Laoperación de calcular un AFD a partir de un AFN es muy común y, por ello, se han desarrollado métodos para hacerlo. El más sencillo y eficiente es el siguiente:
1.- Se construye una tabla en la quecada columna está etiquetada con un símbolo del alfabeto de entrada y cada fila se etiqueta con un conjunto de estados.
2.- La primera fila se etiqueta con {q0}, y en cada entrada de la tabla se...
Un Autómata Finito No Determinista (AFN) se define como una quíntupla de la siguiente manera:
A= (Q, T, λ, q0, F) donde:
Q = Conjunto finito y no vacío deestados,
T = Alfabeto de entrada,
λ = Función de transición que toma como argumentos un estado de Q y un símbolo de T, y devuelve un subconjunto de estados de Q.
q0 = Subconjunto de Q que representa alconjunto de estados iniciales (a diferencia de los AFD, los AFN pueden admitir varios estados iniciales).
F = Subconjunto de Q que representa al conjunto de estados de aceptación (estados finales).Los Autómatas Finitos No Deterministas, también llamados AFN, se caracterizan porque, a diferencia de los AFD, en un estado puede haber más de una transición posible para un mismo símbolo de entrada(alfabeto). Es decir /λ(a)/ ≥ 1 para algún "q" perteneciente a Q y para algún símbolo "a" perteneciente a T.
Ejemplo : Según el siguiente autómata :
Donde λ(q0,01)=λ(λ(q0,0),1)=λ({q0,q1},1)={q0,q1}.
Otra diferencia importante de los AFN con respecto a los AFD es la posibilidad de tener más de un estado inicial.
El lenguaje aceptado por un AFN es el conjunto de cadenas tales que después deser analizadas, el AFN ha logrado alcanzar al menos un estado de aceptación. Tales lenguajes de definen de la siguiente manera:
L(A) = {x perteneciente a T*/ λ (q0, x) intersección F≠ Ø}.
Esimportante establecer que para un lenguaje L aceptado por un AFN, entonces existe un AFD que también acepta el lenguaje L. Es por esto que se hace posible, a partir de un AFN diseñar un AFD equivalente.
Laoperación de calcular un AFD a partir de un AFN es muy común y, por ello, se han desarrollado métodos para hacerlo. El más sencillo y eficiente es el siguiente:
1.- Se construye una tabla en la quecada columna está etiquetada con un símbolo del alfabeto de entrada y cada fila se etiqueta con un conjunto de estados.
2.- La primera fila se etiqueta con {q0}, y en cada entrada de la tabla se...
Leer documento completo
Regístrate para leer el documento completo.