Decidability property.

Question

Intersection of languages produced by two DCFG is a DCFL .

Decidable or not ?

Please give reference for your answer.

Answer 1

Intersection of languages produced by two DCFG may or may not be DCFL. Which means it could be CSL or could be CFL or other.

Intersection of two language of same type is Decidable only for Regular, CSL, Recursive language and Recursively enumerable language but not for CFL or DCFL

Therefore this problem is Undecidable.

Comments

I asked a similar question here https://gateoverflow.in/137855/cfl-decidability and got no satisfactory answer.

---

@rajesh i think the statement that closure properties cant be used to check decidability is only for CFG's

because when we tell union of two CFL is CFL...it not only means it can be CFL...it can also be DCFL in some cases

so if the question says CFL U CFL = CFL then may be it can cause undecidability

correct me

---

If a language is closed under some property

that means , it will be certainly decidable under this.

But if a language is not closed under some property , that means it may or maynot be decidable under that condition

So, Intersection of languages produced by two DCFG is a DCFL .

is may or may not decidable

Because as the language is DCFL , it can be regular too

In that case it will be decidable