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?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.