I am trying to find the regular expression for the language recognized by the following NFA:
$$K=\{1,2,3\},$$
$$\Sigma=\{x,y,z\},$$
$$s(\text{initial state}) = 3,$$
$$F(\text{final state}) = \{1\}.$$
Transition relation $= \{(1,x,2), (3,z,1), (2,y,1), (3, z, 3)\}$
My current idea is that it is $(xyz)^*$ because it has to end with $x, xy$ or $xyz$ and these strings can be looped any number of time but I'm not sure that this is correct.
If anyone had any hints or ideas I would appreciate it very much. Thank you.
Best Answer
You are close. Basically there are two loops: $ca$ from $q_0$ back to itself and $cb$ from $q_1$ over $q_2$ back to $q_1$. As $q_0$ is our final state, we need to combine those loops to get $$ L=(c (cb)^* a)^* $$ Why does this work? If you are in $q_1$ you can either go the $cb$ loop as long as you want or you go $a$ to finish and then you can start again by going to $q_1$ using $c$