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?

  • 1
    $\begingroup$ Based on a quick check, it seems that the expressions are correct. Some of the regular expressions could be simplified (for example $((aa)^*|(bb)^*)^* = (aa|bb)^*$ and the last one seems to be equivalent to $(bb)^*(a|bab)(aa|bb)^*a$, although such simplifications would make their origin less clear. As for the first question -- I believe it's more of an exercise in applying a particular algorithm, rather than something that'd be "useful" for human. On the other hand, it's certainly simple enough for a computer to use. $\endgroup$ Dec 30, 2013 at 0:02

1 Answer 1


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

  • $\begingroup$ Thanks for the answer. I did not create that automaton, it was given in a homework exercise. $\endgroup$ Dec 30, 2013 at 13:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .