¿Cómo convertir una gramática común a expresión regular?

Question

¿Hay algún algoritmo o herramienta para convertir la gramática regular en expresión regular?

Answer 1

Respuesta de dalibocai:

Mi objetivo es convertir la gramática regular a DFA. Finalmente, encontré una herramienta excelente: JFLAP.

Answer 2

El algoritmo es bastante sencillo si puede calcular un autómata a partir de su expresión regular. Una vez que tengas tu autómata. Por ejemplo, para (aa*b|c), un autómata sería (flechas van a la derecha):

  a 
     /\ 
     a \/b 
-> 0 ---> 1 ---> 2 -> 
    \___________/ 
      c 

A continuación, sólo "enumerar" las transiciones como reglas. A continuación, considere que 0, 1 y 2 son símbolos no terminales y, por supuesto, a, byc son los tokens.

0: a1 | c2 
1: a1 | b2 
2: epsilon 

o, si no desea los lados derechos vacíos.

0: a1 | c 
1: a1 | b 

Y, por supuesto, de la vía en la otra dirección proporciona un medio para convertir una gramática regular en un autómata, por lo tanto, una expresión racional.