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?

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

2 Answers 2

Reset to default
1
$\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}

Improve this answer
$\endgroup$
0
$\begingroup$

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

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.