Autómata Finito Determinista (AFD) es un autómata finito en
donde δ (delta) es una función de transición, es decir, que para cada par
(estado actual y símbolo de entrada) le corresponde un único estado siguiente.
Ejercicio 1: Obtenga un AFD dado el siguiente lenguaje
definido en el alfabeto Σ= {0,1}. El conjunto de cadenas que inician en “0”.
Ejercicio 2: Obtenga un AFD dado el siguiente lenguaje
definido en el alfabeto Σ= {0,1}. El conjunto de cadenas que no contienen a la
sub-cadena “01”.
Ejercicio 3: Obtenga un AFD dado el siguiente lenguaje
definido en el alfabeto Σ={a,b,c}. El conjunto de cadenas que inician en la
sub-cadena “ac” y terminan en la sub-cadena “ab”.
Autómata Finito No Determinista (AFND) es un autómata
finito en donde δ no es necesariamente una función de transición, es decir, que
para cada par (estado actual y símbolo de entrada) le corresponde cero, uno,
dos o más estados siguientes, Normalmente la relación de transición para un
AFND se denota con ∆.
Ejercicio 1: Obtenga un AFND dado el siguiente lenguaje
definido en el alfabeto Σ= {0,1}. El conjunto de cadenas que contienen a la
sub-cadena ”01”.
Ejercicio 2: Obtenga un AFND dado el siguiente lenguaje
definido en el alfabeto Σ= {0,1}. El conjunto de cadenas que terminan en 1.
Ejercicio 3: Obtenga un AFND dado el siguiente lenguaje
definido en el alfabeto Σ={a,b,c}. El conjunto de cadenas que inician en la
sub-cadena “ac” y terminan en la sub-cadena “ab”.
No hay comentarios:
Publicar un comentario