# Regular expression and Right Regular grammar for decimals starting with 1 ending with 9?

I was trying to do the following:

Consider the set of all strings over the alphabet {0,1,2,9} that are decimal numbers beginning with 1 and ending with 9 and having exactly one decimal point (.). For example 12.9, would be a valid decimal number while 0.129 would be not since it does not begin with 1.

but it didn't seem to work:

1(0|1|2|9)*.(0|1|2|9)*9


or

S::=1X
X::=E|0X|1X|2X|9X|Y
Y::=.Z
Z::=E|0Z|1Z|2Z|9Z|A
A::=9


Why? Whats the correct answer?

• The alphabet is mentioned twice in the question. Do you have two copies of decimal numbers that are concatenated? If so, take: S -> S'S', where S' generates a decimal number A.B, where A -> 1N and B ->N9, and where N contains 0 or more digits. – Ashwin Ganesan Nov 20 '19 at 5:33
• @AshwinGanesan somehow the copy pasting screwed that up. Only 1 alphabet, its been updated. – Charlie Parker Nov 20 '19 at 15:27
• Why do you think it doesn't work? – Yuval Filmus Nov 20 '19 at 16:54

## 1 Answer

Your regular expression is correct, however, your grammar isn't. Assuming $$E = \varepsilon$$, you can derive words like $$S \to \mathtt{1}\,X \to \mathtt{1}\,\varepsilon = \mathtt{1}$$.

A right regular grammar might look like this: \begin{align} S &::= \mathtt{1}\,A\\ A &::= \mathtt{0}\,A \mid \mathtt{1}\,A \mid \mathtt{2}\,A \mid \mathtt{9}\,A \mid B\\ B &::= \mathtt{.}\,C\\ C &::= \mathtt{0}\,C \mid \mathtt{1}\,C \mid \mathtt{2}\,C \mid \mathtt{9}\,C \mid D\\ D &::= \mathtt{9} \end{align}