Modelo 1
Dada a expresión regular (a+b)*cc(b+a)*
Debuxa o autómata mínimo determinista completo equivalente
Abrimos el JFlap y seleccionamos la opción “Regular Expression”
nos aparece una ventana para introducir la expresión regular, la introducimos
primeramente tendremos que transformarla en un autómata seleccionamos la opción “Convert to NFA” en el menú “Convert” nos abrirá una ventana para iniciar la conversión.
Pinchamos en el botón “Do All” y en “Export” con lo que obtendremos un autómata que acepta las mismas palabras que la expresión regular.
este autómata no es mínimo por lo tanto debemos minimizarlo para eso debemos transformarlo en un autómata determinista, para ello seleccionamos la opción “convert to DFA” en el menú “Convert”
Pinchamos en el botón “Complete” y luego en “Done” con lo que aparecerá una nueva ventana con el autómata determinista
Este autómata determinista puede no ser mínimo así que lo necesitamos minimizar, para ello seleccionamos la opción “Minimize DFA” en el menú “Convert” lo que nos abrirá una nueva pestaña para realizar la conversión
Seleccionamos el nodo raíz del árbol “El que no tiene ningún nodo superior” y pinchamos en “Complete Subtree” para luego pinchar en “Finish” con lo que creara una nueva ventana para la minimización
pinchamos en “Complete” y en “Done” lo que nos creara una nueva ventana con el autómata mínimo
pero este autómata no es completo para eso introduciremos un estado de error al que dirigiremos todas las transiciones que no pertenezcan al autómata.
Indica si dita expresión regular e equivalente a seguinte gramática, e o proceso seguido para averigualo.
- S- -> B
- A -> ε
- B -> C
- C -> B
- I -> A
- C -> D
- E -> F
- I -> H
- H -> J
- K -> I
- J -> L
- O -> K
- M -> K
- Q -> C
- D -> cE
- H -> I
- P -> R
- R -> aT
- N -> aO
- P -> U
- L -> bM
- J -> N
- V -> Q
- F -> cG
- B -> P
- G -> H
- T -> Q
- U -> bV
Abrimos el JFlap y creamos una gramática nueva
una vez insertada la gramática necesitamos convertirla en un autómata para verificar si es equivalente al autómata mínimo del apartado anterior para ello seleccionamos la opción “Convert Right-Lineal Grammar to FA” en el menú “Convert” nos abrirá la siguiente ventana.
pinchamos en “Show All” para seleccionar todas las producciones, y en “Export” lo que nos creara una ventana con un Autómata equivalente a la gramática
Ahora es el momento de comprobar la equivalencia entre autómatas para ello abrimos el autómata mínimo completo del apartado anterior y en la ventana de cualquiera de los dos autómatas seleccionamos la opción “Compare Equivalence” en el menú test nos abrirá una ventana preguntado que autómata queremos comparar y nos mostrara que SON EQUIVALENTES
2 Dada a gramatica
S-> S mais S | S cuadrado | S cubo | raiz S | X
X-> XX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Indica si acepta as seguintes expresións, e en caso afirmativo, obter o árbore de derivación proporcionado polo JFlap
Abrimos JFlap y seleccionamos la opción Grammar
para modelar la gramática deberemos cambiaremos las palabras mais por a, cuadrado por b, cubo por c y raiz por d. Modelamos la gramatica
para obtener el árbol de derivación seleccionamos la opción “Brute Force Parse” en el menú “input” lo que nos abrirá la siguiente ventana
introducimos la palabra a probar en la caja de texto input y pinchamos en “Start”
luego pincharemos en step hasta que nos complete el árbol de derivación
- 00 mais 15 cubo (00a15c)
- raiz 123 cuadrado (d123b)
- 7 mas raiz 3 (7ad3)
A min non me da que sexan equivalentes a primeria expresión regular e a gramatica xD
¿e os automatas son iguais que os que fixen eu?
Si que son equivalentes, esta ben. Perdón pola pérdida de tempo xD