3

Is there an algorithm to convert any regular expression to a right linear grammar? I am familiar with the algorithm to convert a simple regex to CFG. Right linear grammars have stricter rules. A -> a B or A -> a . This makes constructing the algorithm difficult.

Prithvi Raj
  • 31
  • 2
  • 4
  • I don’t remember the normal algorithm for the transformation regex→CFG by heart but doesn’t it produce a linear grammar anyway? – Konrad Rudolph Dec 16 '12 at 14:57
  • 1
    possible duplicate of [Constructing an equivalent Regular Grammar from a Regular Expression](http://stackoverflow.com/q/13816439/1048572) – Bergi Dec 20 '12 at 07:17

1 Answers1

3

There is algorithmic way to convert a Regular Expression(RE) into Non-Deterministic-Finite-automata(NFA) [1] [2] [3]
Also there is alogorithims to convert DFA into Right-Linner-Grammar (RLG). [1] [2]

So of-course their is algorithmic way to convert a RE into RLG.

I think you could like to learn this Constructing an equivalent Regular Grammar from a Regular Expression

Community
  • 1
  • 1
Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208