3,114 views
4 votes
4 votes

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?

1 Answer

5 votes
5 votes

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.

Related questions

0 votes
0 votes
0 answers
2
baofbuiafbi asked Nov 14, 2023
141 views
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...
0 votes
0 votes
0 answers
3
baofbuiafbi asked Nov 14, 2023
142 views
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
0 votes
0 votes
0 answers
4
Abhipsa Panda asked May 24, 2022
148 views
How is equality problem for DCFL decidable?