# How to figure out if a language is recognizable by a finite state machine FSM

I have a finite state machine FSM like below.

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

$$L=0^*1(10)^*(00^*1(10)^*)^*$$

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

Then

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

and

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

So

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