0 votes 0 votes Equality and completeness problem for DCFL and CFL undecidable? Theory of Computation theory-of-computation + – manisha11 asked Oct 21, 2018 manisha11 712 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Equality and completeness problem for DCFL: Decidable Equality and completeness problem for CFL: undecidable https://gatecse.in/grammar-decidable-and-undecidable-problems/ himgta answered Oct 21, 2018 himgta comment Share Follow See all 6 Comments See all 6 6 Comments reply manisha11 commented Oct 21, 2018 reply Follow Share saw this somewhere, therefore confused.. 0 votes 0 votes Verma Ashish commented Oct 21, 2018 reply Follow Share Manisha one entry is wrong in your table.. Completeness problem is decidable for dcfL. 0 votes 0 votes manisha11 commented Oct 21, 2018 reply Follow Share 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 votes 0 votes Verma Ashish commented Oct 21, 2018 reply Follow Share 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 votes 0 votes manisha11 commented Oct 21, 2018 reply Follow Share Are you sure? any reference? 0 votes 0 votes Verma Ashish commented Oct 21, 2018 reply Follow Share 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/ 1 votes 1 votes Please log in or register to add a comment.