|
Título: Como se hace este autómata, alguien que me de una solucion Publicado por: verakra en 28 Marzo 2019, 00:20 am HE BUSCADO EN VARIAS PARTES Y NO HE PODIDO DAR CON UNA SOLUCION
:-( :-( ->Construya el AFN que reconozca el lenguaje de todas las cadenas en base 3 que pueden iniciar en 00 o 22, deben contener 021 y terminar en 11, posteriormente conviertalo en un AFD. Dibuje los automatas y muestre la tabla de transicion de estados, as como el proceso de conversIon. -> Es posible construir un AFN con 3 estados que reconozca el lenguaje vacIo? Título: Re: Como se hace este autómata, alguien que me de una solucion Publicado por: Serapis en 31 Marzo 2019, 19:21 pm Puedes partir creaando la gramática de dicho lenguaje, ya que solo está explicado en prosa... (pondré en negrita las producciones para dicha gramática).
Al decir 'cadenas en base 3', podemos suponer muchas cosas, pero dado el ejemplo del enunciado, se entiende que puede acotarse el lenguaje al uso de solo 3 símbolos para dicho alfabeto: '0', '1' y '2'. Hubiera sido más practico elegir 'A', 'B', 'C', para que quede clara y patente la diferencia entre símbolos y estados., así que quedará un poco lioso... Estas son todas las reglas de producción para dicho lenguaje 0 - Luego los terminales son (los símbolos que admite el lenguaje): char := "0"|"1"|"2" 1 - Los no terminales: ini := "00"|"11" medio := "021" fin := "11" 2 - Luego tu gramática para dicho lenguaje sería: S := ini char* medio+ char* fin Que puede leerse: Es una cadena válida de esta gramática si empieza por 'inicial', contiene cualesquiera 'caracter' (0, 1 o más), tiene al menos un 'medio' y detrás podría tener más 'caracter' (0 1 ó más) y acaba en 'final'. Doy por hecho que deberías conocer el metalenguaje BNF (EBNF), si no fuera el caso... te explico los metasímbolos: '|' expresa un valor elegible libremente entre varias opciones (una alternativa) '[ ]' expresa que es opcional, puede o no aparecer. '*' expresa repetición 0, 1 o más apariciones, es equivalente a '[ ]' '+' expresa repetición, al menos 1 vez debe aparecer. A partir de aquí se podría describir fácilmente una tabla de transición de estados entre tokens, La tabla de transición resumida al estados de aceptación de cada estado sería: Nota que aquí se ha tomado como estado cada token del lenguaje (resulta más sencillo). Aunque no está completo (exige describir el estado de transición para cada token) |-----------------| | e | Lista | |-----------------| | 0 | 1, 2 | ini | 1 | 1, 2 | char | 2 | 2, 3, (4) | medio | 3 | 3, (4) | char | 4 | - | fin |-----------------| La tabla de transicion para detectar el token 'ini' ----------------| est| símbolos | e |'0'|'1'|'2'| ---------------| 0 | 1 | 2 | - | 1 |(3)| - | - | 2 | - |(3)| - | (3)| es el estado de aceptación: ini Si aparece un '0', pasa el estado 1, desde el estado 1 solo puede evolucionar al estado 3 (apareciendo otro '0'). Si aparece un '1' pasa al estado 2, desde el estado 2 solo puede evolucionar al estado 3 (apareciendo otro '1'). El estado 3 es el estado de aceptación... cualquier otro estado se considera error. El AFN para 'ini', sería (dado lo mal que se puede dibujar con caracteres): simb ---> '0'---> '0'---> (3) estd ---> 0 ---> 1 ---> (3) (de un símbolo '0' se pasa al simb ---> '1'---> '1'---> (3) estd ---> 0 ---> 2 ---> (3) Del mismo modo se puede proceder para detectar el resto de tokens. Integrarlo todo en una sola tabla de transición, no es más complejo... Es decir si primero defines la tabla de transición para cada token, y en cada token consideras el estado 0, como el punto inicial, trasladarlo a una sola tabla, es mover los estados de un estado relativo a uno absoluto. Y por ejemplo del estado 3, se puede evolucionar al estado 4, desde el 4 se puede evolucionar al 4 o al 5 (solo si '0', si evoluciona a 5), nótese que siguiendo el token 'medio' debe evolucionar al estado 6, sino evoluciona de nuevo al estado 4 ('char')... Tras el estado medio, igualmente puede evolucionar hacia tokens 'char' ó a 'fin'... Aquí la tabla de transición AFD canónica de estados para dicha gramática (nota que falta insertar la parte del token 'ini): |------------------------| |est| símbolos | | e | '0' | '1' | '2' | |------------------------| |insertar aquí la tabla del token 'ini' | 3 | 5 | 4 | 4 | | 4 | 5 | 4 | 4 | | 5 | 4 | 4 | 6 | | 6 | 4 | 7 | 4 | | 7 | 8 | 9 | 8 | | 8 | 8 | 9 | 8 | | 9 | 8 | (10) | 8 | |------------------------| El estado 10, es el estado de aceptación de la cadena de entrada para la gramática de dicho lenguaje. Nota que el estado 4 y 8 son los estados de 'char'.... solo desde el estado '0' para 'char' se puede avanzar al estado del token 'medio', o regresar al estado 4 del token 'char', de modo similar para ir del estado 8 al 9 del token 'fin'. es decir un intento de evolucionar desde 4, a los estados 5, 6 y 7, puede devenir de nuevo al estado 4... El automata finito determinista, es un caso especial (optimizado) del AFN, cambia respecto del AFN, en que no contempla el conjunto vacío y en que de cada nodo solo puede salir un nodo... ...y hasta aquí te puedo decir, porque si no, ya te hago la tarea completa... Creo que tienes suficiente desarrollo para terminar de completarlo. El asunto es si entiendes del tema o no... porque no has puesto una mísera línea de lo que tengas hecho hasta ahora. Si tienes alguna duda, plantea la pregunta específica... si no asumiré que no tiene ni idea de por donde tomarlo y solo quieres que te hagan la tarea... p.d.: Sería interesante aclarar algunos puntos, pero si no hay feedback, no vale la pena perder el tiempo. |