I'm given the DFA shown below and need to find regular expressions for the following languages: $L_{1,2}^0, L_{2,1}^6, L_{2,5}^4, L_{2,3}^5, L_{1,3}^5$.
The language $L_{p,q}^r$ is defined as $L_{p,q}^r=\{x_1...x_n \in \Sigma^* : \delta(p,x_1...x_n)=q$ and for $i=1,...,n-1$ $\delta(p,x_1...x_i)\leq r\}$- The reason for introducing this notation is the following concept:
In my lecture notes it says that for an automaton with states $Q=\{1,...,m\}$ it follows that $L_{p,q}=L_{p,q}^m$ and we can then find regular expressions for $L_{p,q}$ by making use of the following formula $L_{p,q}^{r+1}=L_{p,q}^r\cup L_{p,r+1}^r(L_{r+1,r+1}^r)^*L_{r+1,q}^r$ and reducing until $r=0$, for which regular expressions can easily be found.
My first question is: Is that a useful concept? I have found this to be extremely time consuming for automata with more than 3 states. Does it ever make sense to apply this?
Finally for the given languages I have found the following regular expressions:
$L_{1,2}^0 : a$
$L_{2,1}^6$ : I don't think there is any input that lets the given DFA go from state 2 to 1
$L_{2,5}^4 : (aa)^*b$
$L_{2,3}^5 : ((aa)^*|(bb)^*)^*a$
$L_{1,3}^5 : (bb)^*(a((bb)^*|(aa)^*)^*a)|(bab((bb)^*|(aa)^*)^*a)$
Are these regular expressions correct?
Answer to the first question. Yes, this algorithm, due to McNaughton-Yamada, is a useful concept, at least theoretically. In practice, one may prefer to solve linear equations to pass from an automaton to a regular expression.
Your exercise. Did you find this automaton by yourself? It looks like you were trying to solve this question and found this automaton which is not minimal: you can merge the states 1 and 3 and the states 4 and 6. Then with only four states, the algorithm is much more manageable...