The Gateway to Computer Science Excellence
0 votes
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.

in Theory of Computation by (29 points) | 72 views
0
i am getting 1) answer both decidable
0

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

0

@utkarshkosta answered :p

1 Answer

+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...
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.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,192 answers
193,988 comments
94,859 users