The Gateway to Computer Science Excellence
0 votes
Equality and completeness problem for DCFL and CFL undecidable?
in Theory of Computation by Active (2.3k points) | 101 views

1 Answer

+1 vote
Equality and completeness problem for DCFL: Decidable

Equality and completeness problem for CFL: undecidable
by Active (3.7k points)

saw this somewhere, therefore confused..

Manisha one entry is wrong in your table..

Completeness problem is decidable for dcfL.
I suppose equality and completeness problem is drawn wrong.
DO you know, about:

Is intersection of languages of same type decidable/ undecidable in CFL, CSL, RL, and REL?

I read somewhere that everything for REL is undecidable but then read that 'Is intersection of languages of same type' is Decidable for REL?
Intersection of languages of same types is decidable only for regular languages. And for all others(dcfl,cfl,csl,rl,rel) it is undecidable..
Are you sure?
any reference?

I read it from r-b-r lectures..i don't have any solid reference..

I get confused if i merge the concept of decidability along with closure property ((for proving anything))...

It's interesting--

A chart for decidability

Related questions

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,737 questions
57,370 answers
105,272 users