1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ Yes, you are right. Here is the same exercise task from another semester: Link There you have the correct regular expression and the same automaton. $\endgroup$ – dtt Jul 12 '16 at 11:03
  • $\begingroup$ @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)$? $\endgroup$ – Sora. Jul 12 '16 at 11:10
  • 1
    $\begingroup$ Yes, both expressions are the same. $\endgroup$ – dtt Jul 12 '16 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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