So I've got the regex /[1-9][0-9]*(\.[0-9]*[1-9])?/ and I'm trying to write a regular grammar for it.

I started off like this:

S ∶≔ EAB
A ∶≔ DA | ε
B ∶≔ .AE | ε 
D ∶≔ 0 | 1 |  2 | 3 |  4 | 5 |  6 | 7 |  8 | 9
E ∶≔ 1 | 2 |  3 | 4 |  5 | 6 |  7 | 8 |  9

But I realised that this does not follow Chomsky's rules for regular grammars. So I was wondering how could I adapt this logic into proper notation.


EDIT: So below is the NDFA generated from the regex above:

enter image description here

  • $\begingroup$ Careful: not every (programmers') regexp defines a regular language. $\endgroup$ – Raphael Apr 28 '17 at 5:08

Regular grammars (of the right-regular variety) are essentially equivalent to NFAs, in the sense that they include roughly the same information. Once you convert your regular expression to an NFA, you can easily construct from it a right-regular grammar.

What doesn't seem possible is adapting your logic to construct a regular grammar. Unfortunately, there is no simple way to convert an arbitrary context-free grammar to a regular one; indeed, it is undecidable to determine whether a given context-free grammar corresponds to a regular language.

| cite | improve this answer | |
  • $\begingroup$ It can be fairly easy to define a regular grammar from the language generated by a regular expression. But in this case, I can't seem to figure out how I would write this expression in the grammar. $\endgroup$ – rshah Jan 27 '17 at 22:13
  • $\begingroup$ You would first convert the regular expression to an NFA, and then convert the NFA to a regular grammar. Both conversions have simple algorithms for accomplishing them. $\endgroup$ – Yuval Filmus Jan 27 '17 at 22:18
  • $\begingroup$ I added the NDFA/NFA generated from the regex, how can i read it into the grammar $\endgroup$ – rshah Jan 27 '17 at 22:25
  • $\begingroup$ Take it as an exercise. The basic idea is to have each non-terminal correspond to a state, and each production rule correspond to a transition or to a final state. If you are using epsilon transitions, you need to eliminate them first. $\endgroup$ – Yuval Filmus Jan 27 '17 at 22:26
  • $\begingroup$ Can a start symbol S ::= εD, D ::= 0|1|2|..|9 ? $\endgroup$ – rshah Jan 27 '17 at 22:33

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.