Other Decision Problems for FSAs

We use a FSA to answer a question of the form: ``is $x$ in the language $L$?''. This is known as a decision problem, since the answer will be ``yes'' or ``no''. We can pose other decision problems for regular languages:

DP1

For any regular language $L$, is $L\, =\, \emptyset$?

DP2

For any two regular languages $L_1$ and $L_2$, is $L_1\, \subset\, L_2$?

DP3

For any two regular languages $L_1$ and $L_2$, is $L_1\, =\, L_2$?

Once again, we approach these problems by examining the corresponding FSAs. The corresponding FSA decision problem, and the decision algorithm, for the above are:

DP1

Given a FSA $M$, does $M$ accept any strings?
A FSA accepts no strings if either there are no final states, or if there is no path from the start state to a final state. To see if this is so, we need to work out which states are ``reachable'' from the start state. Construct the following sets of states:

• $R_0$ just contains the start state
• $R_i$ is all the states in $R_{i-1}$, along with any states reachable in one transition from a state in $R_{i-1}$

We stop the construction when $R_i\, =\, R_{i-1}$ (this has to happen, as there are only a finite number of states altogether). When this happens, just examine the states in $R_i$; if this set doesn't contain any final states, then $M$ accepts no strings.

DP2

Given two FSAs $M_1$ and $M_2$, is the language accepted by $M_1$ a subset of that accepted by $M_2$?
We note that $L_1\, \subset\, L_2$ if and only if $L_1-L_2\, =\, \emptyset$. Thus our algorithm is: construct the machine $M_1 - M_2$ (as in the last section), and apply the algorithm for $[DP1]$

DP3

Given two FSAs $M_1$ and $M_2$, is the language accepted by $L_1$ equal to that accepted by $M_2$?
We note that $L_1\, =\, L_2$ if and only if they are subsets of each other. Thus we simply apply $[DP2]$ twice.