The Gateway to Computer Science Excellence
0 votes
101 views
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
https://gatecse.in/grammar-decidable-and-undecidable-problems/
by Active (3.7k points)
0

saw this somewhere, therefore confused..

0
Manisha one entry is wrong in your table..

Completeness problem is decidable for dcfL.
0
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?
0
Intersection of languages of same types is decidable only for regular languages. And for all others(dcfl,cfl,csl,rl,rel) it is undecidable..
0
Are you sure?
any reference?
+1

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

https://gateoverflow.in/196555/intersection-recursive-languages-decidable-undecidable

https://gateoverflow.in/137855/cfl-decidability?show=140819#c140819

A chart for decidability https://gatecse.in/grammar-decidable-and-undecidable-problems/

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
198,506 comments
105,272 users