0 votes 0 votes Someone explain... L1 ={a^p / p is prime} L2 ={a^p / p is odd} S1 : L1 ∪ L2 is regular S2 : Regular expression of L1 ∪ L2 is a(aa)* A) S1 is decidable(correct) S2 is undecidable(not correct) B) S1,S2 is decidable C) S1 , S2 is undecidable D) None shefali1 asked Dec 6, 2016 shefali1 349 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 1 votes 1 votes L1= {a2, a3, a5, a7, a11, a13 ....} L2= {a1, a3, a5, a7, a9 ....} L1 U L2 = {a1,a2,a3,a5,a7,a9,.....} = {all odd no of a and a2} So S1 is decidable In regex a(aa)* we can't find a2 So S2 is undecidable. target2017 answered Dec 6, 2016 selected Dec 6, 2016 by shefali1 target2017 comment Share Follow See 1 comment See all 1 1 comment reply PEKKA commented Dec 6, 2016 reply Follow Share L1 is Recursive then How can Union of Recursive Lang be Regular ? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes L1 is Recursive L2 is Regular Recursive ∪ Regular is Recursive . Since L1 ∪ L2 is Recursive . hence No regular Expression can be formed . PEKKA answered Dec 6, 2016 PEKKA comment Share Follow See all 2 Comments See all 2 2 Comments reply target2017 commented Dec 6, 2016 reply Follow Share If a language is Recursive it doesn't mean it can't regular. It may or may not. 0 votes 0 votes PEKKA commented Dec 6, 2016 reply Follow Share Yes . Chomskey Heirarchy says so. If a Language is RL then it can be CFL CSL REC and RE also . But converse is not true 0 votes 0 votes Please log in or register to add a comment.