72 views

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.

| 72 views
0
i am getting 1) answer both decidable
0

Yes, that is correct. Can you explain the solution?

0

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

there both statements are decidable... answer 1...
by Boss (12k points)
0

@arvin Thank you so much arvin! This clarified my doubt smoothly! :)

0

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

@arvin

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.
+1
got it :3

you meant to say regular : L1 = a*b*

cfl  = L2 = a^n b^n

L1 intersection L2  =  a^n b^n  ==== > it's dcfl  nor regular .. that means intersection of dcfl with regular we get dcfl right toh ?
+2
Yes intersection of any language with regular will give the other language hence languages are closed under intersection with reg.