4

What is the Standard Algorithm to convert any given Regular Expression(RE) to a Left (or Right) Linear Grammar?

I know I can do this like this (to write Linear Grammar from RE):

RegEx -> NFA -> DFA -> Right Linear grammar.

For a direct approach, I can handle simple regex like (0 + 10)* and create a linear grammar.
But when there is, say, a nested kleene star, its really hard to produce a CFG that is linear, without any well-defined method.

I saw some answers to similar questions here and here. But they do not provide a general algo or does not convert the regex to a linear grammar.

In particular, how do I convert this : (((01+10)*00)*11)* directly to a linear grammar, using some algorithm?

Any help is appreciated.

EDIT

Did some more searching. And got this.
Constructing an Equivalent Regular Grammar from a Regular Expression

Community
  • 1
  • 1
ChesterX
  • 187
  • 1
  • 3
  • 9
  • http://www-cs.ccny.cuny.edu/~vmitsou/304spring10/slides/lineargrammars.pptx from http://www-cs.ccny.cuny.edu/~vmitsou/304spring10/sched.html seems to answer your question. – nhahtdh Apr 11 '13 at 03:34
  • Hi your suggestion was correct in [my answer here](http://stackoverflow.com/questions/13816439/left-linear-and-right-linear-grammars?answertab=votes#tab-top) I made some stupid mistakes. But before I could approve you edit, some other user reject . Now I have corrected my answer. I have request please check again so one new can get correct help. I can help your on this question in evening time...Thanks!! – Grijesh Chauhan Apr 11 '13 at 05:00
  • In short I can answer you that *Standard algorithm* for RE to Linear Grammar(LG) . happens in two steps first from RE to DFA algorithmicly, then DFA to LG algorithmicly(**so search for two algorithms**). Although Its fortunate that We have Regular Expression for Regular Languages Because Regular Expressions and Grammars uses for same purpose but for other then regular languages we don't have any regular expression type mechanism to express the language. Yes for RL we have both RE and Grammar. – Grijesh Chauhan Apr 11 '13 at 05:14
  • [Grako](https://bitbucket.org/apalala/grako)'s only sample project does exactly what you ask. – Apalala Apr 11 '13 at 21:10

1 Answers1

1

Constructing an Equivalent Regular Grammar from a Regular Expression

ChesterX
  • 187
  • 1
  • 3
  • 9
  • Whilst this may theoretically answer the question, [it would be preferable](http://meta.stackexchange.com/q/8259) to include the essential parts of the answer here, and provide the link for reference. – John Dvorak Jun 21 '13 at 07:07