decidability

Question

A = { <R,S> | R and S are regular expressions and L(R) ⊆ L(S) }. Then what about A -

a) Turing recognizable

b) decidable

c) undecidable

d) Turing unrecognizable

Answer 1

b) Decidable

R and S are regular expressions, it means they will generate regular languages only.

Whether a regular language L1 is a subset of another regular language L2 is a decidable Problem.

L1 is subset of L2, it means L2 can generate all strings generated by L1.

L= L1-L2 , then L should be an empty language if L1 is subset of L2.

L= L1 Intersection L2^c 

Complement of a regular language is regular itself, hence Complement of L2 will be a regular language, regular languages are closed under Intersection hence L will be regular too.

it's a Decidable Problem whether a DFA accepts an empty language or non-empty.

Comments

@ manu00x, this is DECIDABLE, 

BUT , can you explain how following is true,

---

@Amrendra Pal, as I explained above it's decidable if L2 is a regular language also.

Answer 2

just fid LR intersction Ls
the dfa u get should be LR.
compare the two dfa
wether two dfa are equal is decidable thus problem is decidable

Answer 3

answer is b, decidable.

steps

1 convert REX to DFA.

2.make compliment machine for s-dfs

3 make product automata.

4 for product automata, check for emptiness.

all 4 are decidable for regular language. So the given problem is also decidable.