The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
158 views

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G.  Which of the following decision problems are decidable?
 I. Whether L(G) is deterministic context free language?
 II.Whether L(G1)∩L(G2) is a context free language, where G1 and G2 are deterministic grammar?

asked in Theory of Computation by Active (3.1k points) | 158 views
0
I) will be decidable. because $reg\cap cfl=cfl$

 Here some of the grammar will give yes as answer, some will give no as ans

So, it will be decidable

II) will be Recursive and decidable

CFL is may or may not closed under intersection, but $dcfl\cap cfl=cfl$ which is possible

So, here also yes and no both ans possible. Hence decidable
0
Where did you get this question from?
0
@srestha What is the "yes"/"no" thing you are talking about?
0
I mean

I)Whether L(G) is deterministic context free language?

here ans could be two types

i) yes L(G) is DCFL

otherwise

ii)No, it is not DCFL

And here as the grammar could be regular,DCFL or CFL

So, it maynot be DCFL always.

That is why answer could be i) or ii)

So, answer for first question will be decidable
0
Okay. But if there are two possible answers, how the problem becomes decidable? In fact if only one answer is possible the problem becomes decidable but the converse is not true.
0
Sir

Recursive problem means , it will be decidable.

and recursive problem means yes and no both ans possible

And only yes cases satisfies for RE problems and no cases satisfies for Non RE problems

Which are undecidable or semi decidable

isnot it?
+2
Nopes. You got it wrong.

If a decision problem (yes/no) has both yes and no answers possible, it is a nontrivial problem. It can be either decidable, semi decidable or not even semi-decidable. The last 2 comes under undecidable category.

Now, if we can make a TM which can CORRECTLY detect both yes and no cases, then the problem is decidable. If the TM detects only the YES cases it is semi-decidable. If not all yes cases can be detected, then the problem is not even semi-decidable.

So to answer a question like this as decidable, you should give a TM or equivalently an algorithm for "how to decide".
0

@Arjun sir, sorry I was away for a couple of days. I found this qustion on geeksforgeeks- https://www.geeksforgeeks.org/gate-gate-cs-mock-2018-set-2-question-50/
 

Could you please let us know the solution.

0

I think then I) and II) both will be undecidable

https://gatecse.in/grammar-decidable-and-undecidable-problems/

0

I think then I) and II) both will be undecidable

Both are Indeed undecidable. I know a valid reduction for Problem 1 But..  for Problem P2, @Arjun Sir, Give some valid logic as I just have some rough picture.intuition of it.

0
Simply can we say

"I. Whether L(G) is deterministic context free language?" and we are searching in domain G, which can be regular, DCFL or NCFL

So, DCFL will not detect correctly, as because  some NCFL also gives also gives "yes" answer in that domain.

So, it will be undecidable

Am I right now?
0
"II.Whether L(G1)∩L(G2) is a context free language, where G1 and G2 are deterministic grammar?"

here G1 and G2 are domain of deterministic grammar(means DCFL and regular)

Now, we are searching for a language which is CFL, which could be outside of domain in case of NCFL

So, it will be undecidable too
0

Whether L(G) is deterministic context free language?" and we are searching in domain G, which can be regular, DCFL or NCFL

So, DCFL will not detect correctly, as because  some NCFL also gives also gives "yes" answer in that domain.

So, it will be undecidable

Am I right now?

Partially right.  Your conclusion is absolutely right But reason is not. Closer properties can not be used to prove Undecidability. Though, Given any CFG, Determining whether $L(G)$ is DCFL or Not, Is undecidable. I have given the proper reduction also in the answer.  

1 Answer

+1 vote

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G.  Which of the following decision problems are decidable? 
 Problem P1. Whether L(G) is deterministic context free language? 

We know that "Regularity problem" for CFLs is Undecidable and "Regularity problem" for DCFLs is Decidable. 
https://gatecse.in/grammar-decidable-and-undecidable-problems/

Regularity problem statement is "Given a CFG $G$, find whether $L(G)$ is Regular or Not ". So, If  "Whether L(G) is deterministic context free language?" were decidable then Regularity problem for CFLs also would be Decidable. 
Because, If you could always say Yes/No for "Whether L(G) is deterministic context free language or Not"  And If you could Always say Yes/No for "Whether a given DCFL is Regular or not" .... Then It would imply that you could always say Yes/No for "Given CFL is Regular or Not" ..which is Not possible because it is undecidable... So, Our assumption of "Whether L(G) is deterministic context free language?" is decidable...Was Wrong.


Problem P2 :  Whether L(G1)∩L(G2) is a context free language, where G1 and G2 are deterministic context free grammar?

Though It is Undecidable...I don't know any concrete proof or reduction from some proven undecidable problem to it. But we could have some rough logic for its Undecidability.

Some points that could add up to its undecidability are that :

1. Neither DCFL Nor CFL are closed under Intersection operation, Hence, Intersection of Two DCFL could even lead to CSL...And then Decidability of Problem $P$ could partially/loosely lead to decidability of "CSL being CFL or not"...

2. We know that It is Undecidable whether the intersection of 2 given CFG’s is a CFL? 
Refer here for undecidable problems for CFLs :  http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/tm-cfl-undecidable.pdf

Since, DCFLs are Not closed under Intersection operation...If we raise both DCFLs to CFLs then for CFLs it would be undecidable to find whether intersection of Two CFL's is CFL or not.

Both of the above points/reasons Do Not prove the Undecidability of Problem P2... But just intuitive idea to remember.


The Point is that You must have seen people giving logic that "Since something is NOT Closed, So it is Undecidable"... like I have seen many a time Students saying with confidence that, "Since CFLs are Not closed under Intersection, So, Finding whether  Intersection of given Two CFLs is CFL or not is Undecidable" ...Which Is Incorrect logic. 

If a language class is closed under operation X then the problem is Decidable. ... It's True.

for eg: "Intersection of two CSL is CSL?" this problem is decidable because it is already proved that CSL follow intersection closure property.

But what if language is not closed under the operation. for eg: problem: "Is intersection of two CFL is CFL or not?"

As CFL/DCFL is not closed under intersection. then Is this true saying that Not following closure operation implies Undecidable problem?.... Answer is "NO...It isn't"

Consider this for instance :
The set of non-empty regular languages isn't closed under intersection, But given two non-empty regular languages, it is Decidable whether their intersection is a non-empty regular language or not.


If someone could give some Valid/Correct Reduction from some already proven  Undecidable problem to Problem P2 or Some valid proof for the undecidability of Problem P2... Please enlighten me as well. TOC is one of my fav subjects and I would be more than curious to know the Valid logic behind it.

answered by Boss (17.5k points)
0

The set of non-empty regular languages isn't closed under intersection

where u got this? 

Neither DCFL Nor CFL are closed under Intersection operation

DCFL closed under intersection, rt? 

+1

The set of non-empty regular languages isn't closed under intersection

where u got this? 

Take any non-empty regular language $L$ and Its complement $L'$...$L \cap L' = \phi $  ..(Though set of Non-empty regular languages are not even closed under Complement operation...because of $\Sigma^*$)

DCFL closed under intersection, rt? 

No. For instance, $a^nb^nc^m \cap a^mb^nc^n = a^nb^nc^n$ which is Not DCFL. 

0

The set of non-empty regular languages isn't closed under intersection

take $a^{*}b^{*}\cap a^{2}b^{4}=a^{2}b^{4}$ , which is regular 

then set of regular language also will be regular

where am I missing?

+1

take a∗b∗∩a2b4=a2b4a∗b∗∩a2b4=a2b4 , which is regular 

then set of regular language also will be regular

where am I missing?

This is One instance. We say some set S is closed under operation X when $a X b = c$,  $\forall a,b,c \in S$ 

 

 

0
Still I have not got ur view.

Take an instance, where this condition will satisfy
0

Take an instance, where this condition will satisfy

Set of all integers under addition operation. 

0
how set of all integers under addition , is not closed under intersection operation?

Can u plz elaborate?

the set could be +ve numbers or -ve numbers or finite set or infinite set

rt?

but how do u tell it is not closed under intersection


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

37,963 questions
45,466 answers
131,322 comments
48,379 users