Let A = { ( R, S) | R and S are regular expressions and L(R) ⊆L(S) }. Show that A is decidable.
Solution
Answer : Given that R and S are regular expressions.
So R and S will generate regular languages. Hence L(R) and L(S)will be regular.
We have to show that whether regular language L(R) ⊆ regularlanguage L(S) .
As we can notice that if Li ⊆ Lj , ThenLi – Lj must be empty .
Here L(R) – L(S) must be empty language…………………….. (i)
As L(R) – L(S) = L(R) ∩ L(S)’ , ( L(S)’ is thecomplement of L(S) )
Regular languages are
OR
OR