0
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\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$ – Ashwin Ganesan Nov 20 '19 at 5:33
  • $\begingroup$ @AshwinGanesan somehow the copy pasting screwed that up. Only 1 alphabet, its been updated. $\endgroup$ – Pinocchio Nov 20 '19 at 15:27
  • $\begingroup$ Why do you think it doesn't work? $\endgroup$ – Yuval Filmus Nov 20 '19 at 16:54
0
$\begingroup$

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}

| cite | improve this answer | |
$\endgroup$

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.