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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,650 questions

56,192 answers

193,988 comments

94,859 users