I have a finite state machine FSM like below.

enter image description here

I want to know which of my languages are recognized by my FSM:

$$L_1=L(0^*1(10)^*(00^*1(10)^*)^*)$$ $$L_2=L((0+1(10)^*0)^*1)$$ $$L_3=L(0^*1(10+00^*1)^*)$$ $$L_4=L(0^*(1(10)^*0)^*1(10)^*)$$

I tried to figure out, but I got confused.

  • There are many - indefinitely many - regular expressions for the same language.
  • There is one minimal FSM for the language.

So the sensible thing to do is to derive the minimal FSM for each of the regular expressions, and see if it equates to the one you have.

How do we do that? Let's try


Define $L / w$ for word $w$ as the set of words $z$ for which $wz$ is in $L$.


$$\begin{align} L/0 &= L\\ L/1 &= (10)^*(00^*1(10)^*)^* \end{align}$$


$$\begin{align} L/10 &= (10)^*(00^*1(10)^*)^*/0\\ &= (00^*1(10)^*)^* / 0 \\ & = 0^*1(10)^*(00^*1(10)^*)^* \end{align}$$


$$\begin{align} L/100 &= L/10/0 \\ & =0^*1(10)^*(00^*1(10)^*)^* / 0 \\ & = L/10 \end{align}$$

So far, it looks like this is an isomorph of the diagrammed FSM, where $L$ equates to $q_0$. I'll leave you to deal with $L/11$ and its progeny.

You can find a description of the algebra in Chapter 5: The Differential Calculus of Events of John Conway's Regular Algebra and Finite Machines.

| cite | improve this answer | |

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.