DHARM266 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE10.5. 3(DP 3)-Membership Problem
Another important decision problem is, for any given string x and regular language L the
question arises; Is x is in L? or whether string x is the member of set of strings of L?
Since, we know that, if L is a regular language then there exists a finite automaton
(DFA) M that accepts L. Now above membership problem can be formulated as, given a DFA M
and a string x, is x is accepted by M?
The solution of above decision problem is determined by the acceptance nature of DFA
M over the string x; i.e.,
l if automata reaches to its final state/s after processing string x then x ∈ L; (yes) so it
is the member of the set of regular language L, or
l if automata is not react to its final state/s after processing string x then x ∉ L; (no) so
it is not the member of L.
To reach on to the solution, above computational procedure ends within finite number
of steps; this fact is because of the deterministic nature of automata M.
Assume M is a n states DFA then if length of the string x is at most n then to reach on to
the final decision it takes O(n) times or in linear time (by assuming that each transition re-
quires constant time).
If L has other representation like NFA or NFA with ∈-moves, then we first convert it to
a DFA and then apply the procedure diseumed earlier.
10.5.4 DP4-Equivalence Problem
Given two sets of regular languages, then the question arises; whether these sets are equiva-
lent or they define same set of regular language? Or,
Given two finite automatons M 1 and M 2 ; are they accept the same language? i.e.;
L 1 = L 2 .[∴ L 1 = L(M 1 ) & L 2 = L(M 2 )]
The solution of above decision problem is fairly simple. If deference of two regular lan-
guages is empty then both are equivalent.
We say that if deference is L where L is given as:
L = (L 1 – L 2 ) ∪ (L 2 – L 1 ) or
⇒ L = (L 1 ∩ L 2 ′) ∪ (L 2 ∩ L 1 ′) where L 2 ′ and L 1 ′ are the complement of L 2 and L 1.
If L = Ø ⇒ only when nothing is common in between one language and complement
of other then both are equivalent.
Else if L ≠ Ø ⇒ regular languages are not equivalent.
Another consequence of equivalence problem is, two regular languages are equivalent if
and only if they are the languages of some common DFA.
Let L 1 is the language of DFA M 1 and L 2 is the language of DFA M 2 and both languages
are equivalent then both DFA M 1 and M 2 certainly converge to a common DFA. In fact, this
DFA is the minimum states DFA constructed from above DFA’s.
So, in this journey of finding solution of equivalence problem we reach to another prob-
lem that is minimization problem that is discussed in the next section.