I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars):

enter image description here

Then I came across many examples that claimed to use these rules to prepare regular grammars from given regex. However I was not able to understand how they are actually using these rules, as they directly gave final regular grammar for given regex. So I decided to try some examples step by step and find whats going on.

Below is one such examples which tries to step by step find RLG and LLG for regex $0^*(1(0+1))^*$. At each step, same color is used to match part of regex getting translated into corresponding part in grammar.

Preparing RLG

enter image description here

Notice that rule in first table says $e^*$ gets translated to RLG productions taking form $S\rightarrow eS | \epsilon$. However in example above, we can see that, to emulate * in regex, we have to put $\epsilon$ in step 2 (green color) as indicated by the rule, but also need to add bunch of other stuff in step 4 (blue color), which are not directly indicated by the rule (though somewhat intuitive extension of the rule).

Preparing LLG

enter image description here

While preparing LLG also, we can see that, to emulate * in regex, we have to put $\epsilon$ (green colored) in step 1 as indicated by the rule, but also need to add bunch of other stuff in step 2 (green colored), which are not directly indicated by the rule (though again somewhat intuitive extension of the rule).

Apart from star closure, there are many stuff that I dont find straight forward or at least requiring extra awareness (that cannot be easily put in step-by-step procedure) while preparing grammar. For example, while preparing RLG, to emulate $0^*$, I can do $S\rightarrow 0S|\epsilon$ as indicated by first table. But in above example, I have to remain extra aware that there is something more $((1(0+1))^*)$ after $0^*$ which forces me to put $A$ in $S\rightarrow 0S | A | \epsilon$ production in step 2. Other facts I should be aware of:

  • While preparing RLG, I should start from left of the regex
  • While preparing LLG, I should start from right of the regex

I observed many more such small points which all I need to be aware at each step of preparing grammar. It makes me feel fuzzy.

Am I going correct with this at all? Is there any book which discuss regex to regular grammar direct conversion, giving clear step by step procedure? Or there is simply no such procedure and I am unnecessarily trying to make it up from examples?

  • $\begingroup$ Converting between regular expressions (!= regexp) and regular grammars is utterly standard (since it's an essential part of proving (constructively) that both concepts are equally powerful) and covered in every introductory textbook on formal languages. $\endgroup$
    – Raphael
    Jan 11 '17 at 19:33
  • 1
    $\begingroup$ Does any book provide exhaustive stepwise procedure to directly convert regular expressions to regular grammars? I know books have discussed procedure for NFA to regular expression conversion but not above direct procedure. Am afraid I havent missed anything from books. I have Ullman and Linz and couple of local publication books. Also didnt get "regular expressions (!= regexp)". $\endgroup$
    – Maha
    Jan 11 '17 at 19:46
  • $\begingroup$ You probably know Thompson's construction; since right-regular grammars are directly equivalent to NFA, that gives you a direct construction. For the other direct, see here. $\endgroup$
    – Raphael
    Jan 11 '17 at 21:14
  • $\begingroup$ "Also didnt get regular expressions (!= regexp)" -- the term "regexp" is typically used to describe the things you find in modern programming languages; they are usually strictly more powerful than plain old regular expressions. $\endgroup$
    – Raphael
    Jan 11 '17 at 21:15

As (briefly) indicated by Raphael in a comment, the only difference between an NFA and a linear grammar is formatting. You can use any algorithm which converts a regular expression to an NFA, and produce a right or left linear grammar instead of the NFA, simply by changing the way you produce output.

Specifically, when you are producing an NFA (with any algorithm) you will perform a series of steps of the form "Add a transition labeled $a$ between $P$ and $Q$", where $a$ is either a terminal or $\varepsilon$, and $P$ and $Q$ are states. To "directly" produce a right linear grammar, implement the above step by producing the production $P\to a Q$ if $a$ is a terminal, or $P\to Q$ if $a$ is ε. Also, implement the step "Mark $Q$ as a final (accepting) state" by outputting the production $Q\to\varepsilon$. (Alternatively, don't put $Q$ in the productions produced for transitions, if you know in advance that $Q$ is a final state.)

If you want to produce a left linear grammar, you need to work with incoming transitions instead of outgoing transitions; for the $a$-transition from $P$ to $Q$, write $Q\to P a$ unless $P$ is the start state, in which case you just use $Q\to a$. (Again, ε transitions are handled by omitting $a$.)

If the unit productions bother you, use an algorithm which produce an ε-free NFA, or produce the NFA and then do an ε closure to eliminate the ε transitions before printing out the grammar.

Any correct regular expression to linear grammar algorithm will be some version of the above procedure (since you could produce the transition table instead of the grammar by once again changing the print format).

  • $\begingroup$ So basically we have to go through NFA route, either directly or indirectly...and the rules I specified in the table in the original question are not sufficient. Right? $\endgroup$
    – Maha
    Jan 16 '17 at 8:54
  • $\begingroup$ @Mahesha999: You don't have to go "through" the NFA route. The point is that the two results are homomorphic; any algorithm which produces a linear grammar also produces an NFA and vice versa, because the only difference is the formatting of the output (one outputs state transitions and the other outputs productions, but aside from punctuation the lines are identical). The algorithm you present in the OP does not satisfy the requirements for either. (But as an exercise, you could modify that algorithm to produce state transitions instead of productions, which might help show the equivalence.) $\endgroup$
    – rici
    Jan 16 '17 at 13:53

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.