1 votes 1 votes Which of the following statements is/are true? I. If L is decidable, LR may or may not be decidable. II. If L⊆{0}*, then L is decidable III. If L≤m {0n 1n│n≥0}, then L is Decidable Shashank Chandekar asked Nov 13, 2016 Shashank Chandekar 362 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes III. If L≤m {0n 1n│n≥0}, then L is Decidable . True L≤m {0n 1n│n≥0}[CFL] CFL is decidable . Decidable goes from right to left so L is also decidable. https://courses.engr.illinois.edu/cs373/fa2011/exams/fa10midterm2sol.pdf Prashant. answered Nov 13, 2016 Prashant. comment Share Follow See all 2 Comments See all 2 2 Comments reply mcjoshi commented Nov 13, 2016 reply Follow Share What about $2^{nd}$ option? 2 votes 2 votes mcjoshi commented Nov 13, 2016 reply Follow Share And in (3) question, what does $\le_m$ mean? 0 votes 0 votes Please log in or register to add a comment.