# Converting a regular expression to a grammar and regular grammar

I am working on a pretty small lab for my university course and I'm having trouble converting a given regex into a set of regular definitions, then into a grammar and finally a regular grammar. I have reviewed the course material given to me and it has given me some understanding of the process, just enough for me to attempt it but not enough for me to be confident in what I'm doing. I have also tried looking for resources online but I could not find anything that helped me understand the concepts any better, if you have any online resources you recommend please let me know I would love to read more on the topic.

My goal for this question is not to get the answers to my lab but rather to help me understand if I'm doing something wrong and how to do it correctly. I will detail the questions as well as my work so far below.

Note: excuse my formatting, I'm not very good at it.

Question

Regex: $$[0−9].[0−9]+e(−)?[0−9]+$$

steps

1.Regex into regular definition

2.Regular definition into grammar

3.Grammar into regular grammar and how many productions does it have?

My work so far

1. I started by converting the regex into definitions, what I ended up with was the following

$$DIGIT → [0-9]$$

$$EXPONENT \rightarrow$$ $$'e'('-')?DIGIT$$

$$DECIMAL \rightarrow$$ $$'.'DIGIT$$ $$EXPONENT$$

$$FLOAT \rightarrow DIGIT$$ $$DECIMAL$$

I'm basing this off of the example shown to me in class, it could very well be incorrect. One of my main concerns here is if I am allowed to have the EXPONENT definition embedded within the DECIMAL definition and how that will affect my later work.

1. My work here is based off of part 1 which could be incorrect, so I will assume my last section was correct and continue working from there.

$$FLOAT \rightarrow DIGIT$$ $$FLOAT2$$

$$FLOAT2 \rightarrow$$ $$'.'$$ $$DIGIT$$ $$EXPONENT$$

$$EXPONENT \rightarrow$$ $$'.'$$ $$'-'$$ $$DIGIT$$

$$EXPONENT \rightarrow$$ $$'e'DIGIT$$

$$DIGIT \rightarrow 0|...|9$$

$$DIGIT \rightarrow DIGIT$$ $$DIGIT$$

This is what I came up with for grammar, I'm not sure about the two $$DIGIT$$ lines in the bottom, I assumed this is how you handle $$[0-9]+$$. The question prompt mentions possibly needing alot of $$FLOATX$$ where $$X$$ is 1,2,3... The fact that I only needed $$FLOAT2$$ while the example in my lecture material needed more makes me think that I missed something there as well.

1. This is the last part where I have to convert the grammar from part 2 into a regular grammar, I will once again be assuming my work in the last step is correct so I can continue on.

This step I'm very lost on, I don't really know where to go to be honest, the work I have on my lecture material does not include enough steps for me to try and understand the logic behind the steps taken. I will leave this one blank.

• I have never heard of "regular definitions" – this is a "less-standard" concept, at the very least. – Yuval Filmus Sep 24 '20 at 7:31
• A regular grammar is essentially the same as an NFA. Regular expressions can be converted mechanically into NFAs using Thompson's construction and its variant, which are very efficient. No creativity is involved. – Yuval Filmus Sep 24 '20 at 7:34
• I think you just want to convert this regex to regular grammar: vasy.inria.fr/people/Gordon.Pace/Research/Software/Relic/… – prime_hit Sep 24 '20 at 10:07