# NFA corresponding to the regular expression α = (a*b | ϵ) (b*(a | ϵ))

I'm currently studying for an upcoming exam in theoretical computer science, but one of the exercises is confusing me: in the exercise sheet it says that the NFA $$M=(\{z_0,z_1,z_2\},\{a,b\},\delta,\{z_0,z_1,z_2\},\{z_2\})$$ corresponding to the regular expression $\alpha=(a^*b|\epsilon)(b^*(a|\epsilon))$ is defined by $$\begin{array}{c|ccc} \delta&z_0&z_1&z_2\\\hline a&\{z_2\}&\{z_1\}&\emptyset\\ b&\{z_0\}&\{z_0,z_2\}&\emptyset \end{array}$$ where $\delta$ is the transition function.

I don't understand how this can be right - if I'm not mistaken, the word $bb$ is an element of $L(\alpha)$ but it's not an element of $T(M)$.

So... basically, my question is: is the exercise sheet flawed or am I misunderstanding the concept of regular expressions?

I think the inner pair of parentheses is out of place - without this pair of parentheses, we get the regular expression $$\alpha=(a^*b|\epsilon)(b^*a|\epsilon),$$ which seems to satisfy $L(\alpha)=T(M)$... can anyone confirm this? (Sorry, I'm a beginner.)
• @HueHang thanks a lot! Another question about the other regular expression in this exercise - do we have to write $\beta$ as $ab^*(a|b|\epsilon)$? Is this not the same as $ab^*(a|\epsilon)$? – Sora. Jul 12 '16 at 11:10