0

It is given that $\Sigma=\{1,2,4,5,7,9\}$ and $L=\{w: w \in \Sigma^{*} \text{ ,w gets divided completely by }5\}$. Could you help me to find a regular expression for this language?

evinda
  • 7,823

1 Answers1

3

If something is divisible by 5 then it ends in zero or five.

So (1|2|4|5|7|9)*5 would characterize your language.

DanielV
  • 23,556
  • I have also an other question..if the language was $L={w: w \in \Sigma^{*} \text{ ,w as a decimal,gets divided completely by }5}$ ,would the regular expression be the same? – evinda Jan 22 '14 at 00:33
  • 1
    I don't know what "as a decimal" means...other than restricting your alphabet to 10 digits. – DanielV Jan 22 '14 at 00:35
  • Yes,it is meant that $w$ consists digits between 0 and 9..So,it is the same regular expression.or not?? – evinda Jan 22 '14 at 11:27
  • 1
    Yes, then it is that same regex because you are also restricted to $\Sigma$ and $\Sigma$ doesn't have any characters that are not digits. If $\Sigma$ had non-digit characters, then it wouldn't have been the same. – DanielV Jan 22 '14 at 15:34
  • Nice...Thank you very much!!!! – evinda Jan 22 '14 at 20:41
  • And something else..if $w$ should get divided completely by 7,then the regular expression wouldn't be like that: $(1|2|4|5|7|9)^{*}7$,right??Because,for example $297$ doesn't get divided completely by 7..But,what can I change then at the regular expression? – evinda Jan 23 '14 at 16:04
  • 1
    @evinda If you want a regex for divisibility by seven, look here: http://codegolf.stackexchange.com/questions/3503/hard-code-golf-regex-for-divisibility-by-7 If you want a simpler state machine for divisibility by seven (using modular arithmetic to represent multiple states as a single integer) then look here : http://www.math.hmc.edu/funfacts/ffiles/10005.5.shtml If you need help with the code for the non regex version, post a question to stack overflow and leave a link here, and I will answer it. – DanielV Jan 23 '14 at 17:42
  • Isn't there a simpler regular expression for the language?? – evinda Jan 25 '14 at 00:28
  • Looks simple to me. – DanielV Jan 25 '14 at 03:05