Is there an algorithm for creating a regular grammar directly from a regular expression? All the discussions and notes I found so far go through an intermediary step of creating an FA for the reg ex and then the regular grammar from the FA. E.g., for a reg ex $a(b|c)*d$, what's the algorithm for figuring out the rewriting rules without first building the FA? I already built the grammar, but did so intuitively, I'd really like to see a generic algorithm that can be applied on any reg ex to build the grammar's productions.


  • $\begingroup$ Nvm, found it in a notebook. And my productions seem ok based on this alg :). $\endgroup$ – user3013202 Nov 20 '13 at 14:23

You can do it by combining grammars.


$A,B,C,...$ will be non-terminals

$a,b,c,...$ will be terminals

$\alpha,\beta, ...$ will be "whatever can be here"

$x$ and $y$ will be regular expressions

The grammar corresponding to a regular expression $x$ will be denoted $f(x)=(N_x,\Sigma,P_x,S_x)$

$f(a)=(\{S\},\Sigma, \{S\to a\}, S)$

$f(x\mid y)=(N, \Sigma, P, S)$

$N=N_x\cup N_y \cup \{S\}$

$P=P_x\cup P_y\cup\{S\to \alpha \mid S_x\to \alpha\in P_x\}\cup\{S\to \alpha \mid S_y\to \alpha\in P_y\} $

The idea is that you want to be able to go one way or the other but if you add $S\to S_a$ and $S\to S_b$, then your grammar isn't regular anymore.

You could want to replace both $S_x$ and $S_y$ and their associated rules but if you do that, if the grammars use $S_x$ or $S_y$ somewhere on the right hand side, it might fail. For example if they represent $a^*$ and $b^*$ in such a way, then instead of $a^*\mid b^*$, your grammar would represent $(a\mid b)^*$ which isn't the same thing.

Here's the grammar for $a^*$:

$S\to \varepsilon$

$S\to aS$

$f(x\cdot y)=(N, \Sigma, P, S_x)$

$N=N_x\cup N_y$

$P=\{A\to bC\mid A\to bC\in P_x\} \cup \{A\to bS_y \mid A\to b \in P_x\}\cup \{A\to S_y \mid A\to \varepsilon \in P_x\} \cup P_y$

The idea is that since your grammar is regular, you'll always have a unique non-terminal until you finish your word with a rule not producing a non-terminal so you simply replace those rules in the first grammar by rules saying to continue on the second grammar.

$f(a*)=(N_a,\Sigma, P_a\cup \{A\to bS_a\mid A\to b\in P_a\}\cup \{A\to S_a\mid A\to \varepsilon\in P_a\}\cup \{S_a\to \varepsilon\}, S_a)$

$f(x^*)=(N_x,\Sigma, P, S_x)$

$P=P_x \cup \{A\to bS_x \mid A\to b \in P_x\}\cup \{A\to S_x \mid A\to \varepsilon \in P_x\}\cup \{S_x\to \varepsilon\}$

Same thing as above but you also take the rules giving simply the non-terminal or $\varepsilon$ to allow to end right away.

  • $\begingroup$ Very good explanation. But for $f(a*)$, won't this break the definition of the regular grammar? I.e., a right lin grammar where, if $S \rightarrow \epsilon \in P$, then $S$ cannot appear in the right hand side of any production? $\endgroup$ – user3013202 Nov 20 '13 at 20:16
  • $\begingroup$ $f(a*)=(N_a,\Sigma, P_a\cup \{A\to bS_a\mid A\to b\in P_a\}\cup \{A\to S_a\mid A\to \varepsilon\in P_a\}\cup \{S\to \varepsilon\}\cup \{S\to S_a\}, S)$ $\endgroup$ – xavierm02 Nov 20 '13 at 22:43
  • $\begingroup$ And if $a$ and $b$ are primitive regexps, for $f(a+b)$ can't one also safely remove $N_a$ and $N_b$ from $N$? And in general, can't unneeded elements be removed from $N$, $P$ as the grammar definition advances from the primitive regexps to the complete regular expression? $\endgroup$ – user3013202 Nov 20 '13 at 22:47
  • $\begingroup$ I don't think disallowing $A\to\varespilon$ when you have $B\to cA$ is useful. Since your grammar is regular, you'll always have at most one non-terminal... It's not like in general grammars where having $A\to\varespilon$ could make it really hard to "execute" because you could generate a lot of non-terminals for nothing. $\endgroup$ – xavierm02 Nov 21 '13 at 11:30
  • $\begingroup$ I updated about $x\mid y$ and no, you can't remove them. $\endgroup$ – xavierm02 Nov 21 '13 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.