What is regular expression and its NFA of a word that accept any number that is divisible by 5?

1.2k Views Asked by At

I was given a task to find RE and NFA for a word that is divisible by 5.

∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  1. String passed to RE could be of any length
  2. You may also allowed to sub divide ∑ into more than one sets

I want to verify my attempted solution.

Let A = {1, 2, 3, 4, 6, 7, 8, 9}  
Let B = {0, 5}

We know the numbers divisible by 5 always end at 0 or 5. Therefore the RE that would accept any number that is divisibly by 5 is

(a*b*)*b

Few examples to verify the RE.

Examples to verify RE

The NFA I drew is

enter image description here

My question is, are my answers correct? If not then what's the mistake I made.

2

There are 2 best solutions below

0
On BEST ANSWER

If you separate zero, i.e. A = {1, 2, 3, 4, 6, 7, 8, 9}, B = {5}, C={0} then you can write RE like this: $(c|((a|b)(a*b*c*)*(b|c)))$

0
On

Let $A = \{0, 1, 2, 3, 4, 6, 7, 8, 9\}$, $B = A \setminus \{0\}$ and $C = \{0, 5\}$. Since a number is divisible by $5$ if and only if it ends with $0$ or $5$, the expression you are looking for seems to be $A^*C$. However, if you take into account that the first digit of a number is never $0$ (except for $0$), then it should be $$ BA^*C \cup C $$