1,584 views
1 votes
1 votes

Let L be a DCFL and R is a regular language. Consider the below given problems.

P : Is L ≠ R?

Q : is R ⊂ L?

Choose the correct option.

  1. Both problems P and Q are decidable.
  2. Both problems P and Q are undecidable.
  3. Problem Q is decidable and P is undecidable.
  4. Problem P is decidable and Q is undecidable.

I understand that Equality problem is decidable and Subset problem is undecidable for DCFL’s, i.e when both languages are DCFL’s.

How do I analyze decidablity for different languages? In this case, for a RL and DCFL.

1 Answer

5 votes
5 votes

here l=dcfl and R= regular language..

statement p:

L ≠ R means L∩R=Φ .since dcfl are closed under intersection with regular langauge = dcfl and now dcfl are closed under emptyness...

so this is decidable...

statement q:

R ⊂ L means R∩L =L . since dcfl are closed under intersection with regular langauge = dcfl  and now dcfl are closed under equivalence...

so this is also decidable...

refer : https://gateoverflow.in/96057/toc-dcfl-closed-under-equivalence-property 

there both statements are decidable... answer 1...

Related questions

0 votes
0 votes
0 answers
3
Na462 asked Jan 21, 2019
713 views
0 votes
0 votes
0 answers
4
Ayush Upadhyaya asked Jan 13, 2019
403 views
From http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf $L_{26}=\{<M>|$ M is a TM such that both L(M) and $\lnot L(M)$ are infinite $\}$I was unable to get...