Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Peter Košinár Dec 30 '13 at 0:02
up vote 1 down vote accepted

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

share|cite|improve this answer
Thanks for the answer. I did not create that automaton, it was given in a homework exercise. – eager2learn Dec 30 '13 at 13:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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