How to convert a regular grammar to regular expres

问题:

Is there an algorithm or tool to convert regular grammar to regular expression?

回答1:

Answer from dalibocai:

My goal is to convert regular grammer to DFA. Finally, I found an excellent tool : JFLAP.

回答2:

The algorithm is pretty straightforward if you can compute an automaton from your regular expression. Once you have your automaton. For instance for (aa*b|c), an automaton would be (arrows go to the right):

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

Then just "enumerate" your transitions as rules. Below, consider that 0, 1, and 2 are nonterminal symbols, and of course a, b and c are the tokens.

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

or, if you don't want empty right-hand sides.

0: a1 | c
1: a1 | b

And of course, the route in the other direction provides one means to convert a regular grammar into an automaton, hence a rational expression.