# Counting number of states from a regular expression

Given the regular expression: $$r=ab+((a+\epsilon)c^*)^*$$. Let A be a non-deterministic automaton that accepts the language of r. How many states are in A? Answer the question without building A explicitly, explain how you got the answer.

I'm having trouble figuring this question out. The answer that was given is: $$5*2+4*2=18$$

With the explanation that for the $$\epsilon$$ regular expression we build an automaton with 2 states.

for each $$\sigma \in \Sigma$$ for the regular expression $$\sigma$$ we build an automaton with 2 states

For concatenating we do not add states and for each union or star operation we add 2 states.

But even with this explanation I'm not quite sure did they reach this answer.

I can understand that we have $$\epsilon$$, so we have 2. Plus we have $$\Sigma = \{a,b,c\}$$ so we do $$2*3$$.

Even with the stars, how do we reach $$5*2$$?

Also I haven't seen this kind of calculation before, are there any additional rules when trying to calculate states from a regular expression?

The rule for the $$\sigma\in \Sigma$$ must be applied each time a letter appears in the regular expression, not only once per letter : you must build a different automata each time the letter appears. If you see it as some kind of digital circuit, you do not want to use the circuit that recognizes $$a$$ in $$ab$$ for the circuit that recognizes $$a$$ in $$a + \epsilon$$.
So you have five letters that appear in $$r$$, that's $$5*2$$ states. Then you have 2 concatenations, two unions and two stars. That's $$2 * 0 + 2*2+2*2 = 4*2$$ states.