1 1 vote L={w(wR)* , w=(a+b)* }. Is this language regular? According to me it should not be regular as we can have strings of form wwR which is not regular but the answer is that its a regular language. Theory of Computation theory-of-computation regular-language + – Xylene 1.5k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
Best answer 2 2 votes 1. L={w(wR)* | w belongs (a+b)* }. Is regular? = w = (a+b)* [because (wR)* is considered null because of * ] (a+b)* contain all strings included in L. 2. L= (wwR)* it is not regular it is CFL . 3. (w)*wR is also regular , since regular is closed under reversal . [(a+b)*]R Prashant. answered Nov 13, 2016 • selected Nov 13, 2016 by Xylene Prashant. comment Share Follow See all 10 Comments 10 10 Comments reply Xylene commented Nov 13, 2016 reply Follow flag If L = {w(wR )+ } then what will it be? 0 0 replyShare mcjoshi commented Nov 13, 2016 reply Follow flag @Anirudh, @Habibkhan I have a doubt. L0 = {w | w belongs (a+b)*} is regular L1 = {$w^r$ | w belongs (a+b)*} is regular closed under reversal. What is the language formed by concatenation of L0 and L1. Means what is $L_0L_1$ ? 0 0 replyShare Prashant. commented Nov 13, 2016 reply Follow flag you take wo independemt things into consideration. 0 0 replyShare Prashant. commented Nov 13, 2016 reply Follow flag language will be [(a+b)*]r = (a+b)* L0 . L1 = (a+b)* .(a+b)* = (a+b)* 0 0 replyShare mcjoshi commented Nov 13, 2016 reply Follow flag Anirudh, I know $WW^R$ is NCFL. Just wanted to know about concatenation. 0 0 replyShare Prashant. commented Nov 13, 2016 reply Follow flag WWr you dont know when mid point come i.e. from where you check Wr so it is not deterministic. in {anbn} we know when 1st b come we have to pop . but in wwr you dont know when to do pop . 0 0 replyShare Xylene commented Nov 13, 2016 reply Follow flag Can u answer my question on which class of language does L = { w(wR )+ } belong to ? @mcjoshi @Anirudh 0 0 replyShare Kaluti commented Nov 13, 2016 reply Follow flag W((w)^(r))^(+) should be non regular 0 0 replyShare Xylene commented Nov 13, 2016 reply Follow flag I know it will be non regular but under which class of language does it come? 0 0 replyShare Kaluti commented Nov 17, 2016 reply Follow flag I think it will be ncfl still 0 0 replyShare Please log in or register to add a comment.
