1 votes 1 votes Can we prove a language is Non-CFL using Diagonalisation ? If yes then how ? Theory of Computation shai-simonson theory-of-computation + – ankitgupta.1729 asked Mar 8, 2018 ankitgupta.1729 460 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Mamta Satywali commented Mar 9, 2018 reply Follow Share Could you please provide the link to that video, I might have understood this then but unable to recollect now. 0 votes 0 votes ankitgupta.1729 commented Mar 9, 2018 reply Follow Share @Mamta , Please check @ 01:15:08 here 0 votes 0 votes Mamta Satywali commented Mar 10, 2018 reply Follow Share What I think, as he too added following in his later lectures- To declare a language L as NON-CFL, we create a TM 'M' which accepts 'L'. Then determine whether M accepts nothing? Case1- If L is actually CFL then- 1. Check encodings of TM and find whether start symbol is a useless symbol/not 2. If yes then M accepts nothing is true otherwise false.Either case we will say L is CFL. In other words, I can say this problem is decidable for CFL. Check here- https://youtu.be/N4L8j5VomAw?t=1227 Case-2: If L is NOT CFL- 1. Suppose this is decidable too. 2. I can easily reduce this problem to Halting Problem which we know by diagonalisation is undecidable, hence above problem is also undecidable. Check here- https://youtu.be/O91-BOS8WrA?t=298 Conclusion- If you say this is decidable then I will say the language is CFL. If you say this is undecidable, then I will say language is NOT CFL 1 votes 1 votes ankitgupta.1729 commented Mar 10, 2018 reply Follow Share @Mamta ,thank u so much for ur response..I m getting u partially now.. since, I have watched till video 9 ...So, I will watch all these videos then I will get back to you if I will have any confusion... Thank you.. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes I THINK Application of diagnalization is to proof Uncountableity of set not for Checking NCFL abhishekmehta4u answered Mar 9, 2018 abhishekmehta4u comment Share Follow See all 2 Comments See all 2 2 Comments reply ankitgupta.1729 commented Mar 9, 2018 reply Follow Share @Abhishek ,bro I know that using Cantor's Diagonalisation method, we can prove that a set is uncountably infinite..but according to Shai sir , "other ways of showing things are not context-free , I could bring in diagonalisation " but he did not show how to do it..that's why I asked this question.. 1 votes 1 votes Jason commented Mar 9, 2018 reply Follow Share IS there any Diagonalization method other than Cantor's? 0 votes 0 votes Please log in or register to add a comment.