The Gateway to Computer Science Excellence

0 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.

- Both problems P and Q are decidable.
- Both problems P and Q are undecidable.
- Problem Q is decidable and P is undecidable.
- 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.

+3 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...

0

.SINCE (

DCFL ARE CLOSED UNDER INTERSECTION WITH REGULAR LANGAUGE )= DCFL AND NOW DCFL ARE CLOSED UNDER EMPTYNESS..

how you came with that conclusion ??

means 2 DCFL lang ain't be close under intersection that I know

and Regular lang is closed under intersection

your answer is right but I just want to know what is your thought behind that statement "DCFL are closed under intesection with regular lang" ???

0

Hint : Take any dcfl and a reg . Language intersect them and see the result... Try once if you have problems. I will explain more.

52,222 questions

59,853 answers

201,033 comments

118,095 users