elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Como se hace este autómata, alguien que me de una solucion
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Como se hace este autómata, alguien que me de una solucion  (Leído 794 veces)
verakra

Desconectado Desconectado

Mensajes: 15


Ver Perfil
Como se hace este autómata, alguien que me de una solucion
« 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?


En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 2.772


Ver Perfil
Re: Como se hace este autómata, alguien que me de una solucion
« Respuesta #1 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.


« Última modificación: 1 Abril 2019, 16:10 pm por NEBIRE » En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
¿Alguien sabe que hace este código?
Seguridad
Demenus 4 2,625 Último mensaje 15 Mayo 2010, 22:44 pm
por [L]ord [R]NA
ALGUIEN PUEDE AYUDARME EN COMO SE HACE ESTE PROGRAMA, en Dev C++ « 1 2 »
Programación C/C++
Ivs_mx 11 15,271 Último mensaje 19 Septiembre 2012, 22:18 pm
por Ivs_mx
¿alguien sabe como se hace este scrip de espera en php?
PHP
Weeken 1 1,502 Último mensaje 22 Septiembre 2012, 03:49 am
por WarGhost
alguien sabe como se hace este script ?
PHP
Weeken 6 3,452 Último mensaje 13 Mayo 2013, 01:32 am
por #!drvy
alguien hace este script?
Scripting
WilkinGraph 5 1,299 Último mensaje 26 Febrero 2014, 15:21 pm
por Eleкtro
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines