1

Could anyone please step me through the process of obtaining a regular grammar from a regular expression? I found few 'tutorials', but I am still unable to turn a more complicated regular expression into a grammar.

How would you tackle ((a+b)*(c|d))+a??

I though of

A -> aB
A -> aA
B -> bA
A -> cC
A -> dC
C -> cA
C -> dA
C -> a
C -> epsilon

But it's obviously incorrect.

Jules
  • 247
  • 2
  • 8
  • Seems nothing that works. I just imagined how it could look like, drew some finite state machines and checked if I get what I want. – Jules Feb 13 '15 at 12:57
  • @rici: Oh, I misread the question, comment removed. But my point still stands regarding it is described in books about automata theory. – nhahtdh Feb 13 '15 at 15:43
  • @Jules Check this [Constructing an equivalent Regular Grammar from a Regular Expression](http://stackoverflow.com/questions/13816439/left-linear-and-right-linear-grammars/13945932#13945932) – Grijesh Chauhan Feb 16 '15 at 04:05

1 Answers1

3

Just work from inside out. Each operator introduces a new non-terminal

 Operator  Grammar     Operator  Grammar
 --------  -------     --------  -------
    R|S     A->R          R*      A->
            A->S                  A->AR

    R?      A->           R+      A->R
            A->R                  A->AR

(Most expositions will also introduce new nonterminals for concatenation; here, I didn't bother. I hope it's not confusing.)

Example:

((a+b)*(c|d))+a?

Sub-          Rewritten with   Rules for
expression    new nonterminal  new nonterminal
----------    ---------------  -----------
a+            A                A->a    A->Aa
a+b           Ab
(a+b)*        (Ab)*            B->     B->BAb
c|d           C                C->c    C->d
(a+b)*(c|d)   BC
(a+b)*(c|d)+  (BC)+            D->BC   D->DBC
a?            E                E->     E->a
(a+b)*(c|d)+  DE               S->DE
rici
  • 234,347
  • 28
  • 237
  • 341