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:




Why? Whats the correct answer?

  • $\begingroup$ 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. $\endgroup$ Nov 20, 2019 at 5:33
  • $\begingroup$ @AshwinGanesan somehow the copy pasting screwed that up. Only 1 alphabet, its been updated. $\endgroup$ Nov 20, 2019 at 15:27
  • $\begingroup$ Why do you think it doesn't work? $\endgroup$ Nov 20, 2019 at 16:54

2 Answers 2


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}


A regular expression for your language is: $$ 1(0\cup\ 1\cup 2\cup 9)^*.(0\cup\ 1\cup 2\cup 9)^*9.$$


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.