If L1 and L2 are regular languages, then there is an algorithm for determining i

Question

If L1 and L2 are regular languages, then there is an algorithm for determining if L1 is a subset of L2.

Let M1 and M2 be DFAs for L1 and L2 respectively. Create the combination machine M combining M1 and M2.  

Determine the reachable states in M. Call the set of reachable states R.

If there is a state <x,y> in R (note x is a state in M1 and y is a state M2) such that x is an accept state in M1 and y is a reject state in M2, return false. Else return true.

Using this algorithm as a model, describe an algorithm that would determine if L1 and L2 are disjoint languages (i.e. L1 and L2 contain no strings in common.)

Explanation / Answer

Let M1 and M2 be DFAs for L1 and L2 respectively. Create the combination machine M combining M1 and M2.  

Determine the reachable states in M. Call the set of reachable states R.

If there is a state <x,y> in R (note x is a state in M1 and y is a state M2) such that x is an accept state in M1 and y is also an accept state in M2, return false. Else return true.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.