66 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?

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.