1 votes 1 votes Are (bx)* b and b(xb)* equivalent? Theory of Computation theory-of-computation regular-expression + – Aegon asked Jan 17, 2017 • retagged Jun 4, 2017 by Arjun Aegon 865 views answer comment Share Follow See 1 comment See all 1 1 comment reply Pavan Kumar Munnam commented Jan 17, 2017 reply Follow Share yes they are deriving the same sets 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes Deriving same strings try writing string set for both language. It will be same Tendua answered Jan 22, 2017 Tendua comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes No . Because (bx)*b are deriving all strings ending with b And b(xb)* are deriving all strings starting with b. Moreover first one can derive the string "bbxxb" whereas second one cannot derive this string. Hence, they are not equivalent. nandini gupta answered Jan 17, 2017 nandini gupta comment Share Follow See all 4 Comments See all 4 4 Comments reply Prateek Yadav 2 commented Jan 17, 2017 reply Follow Share you have taken wrong example bbxxb can not derive from any of set Even both are equivalent since both are generating string that start and ends with b. 0 votes 0 votes nandini gupta commented Jan 17, 2017 reply Follow Share Why (bx)*b cannot derive "bbxxb"? 0 votes 0 votes Tendua commented Jan 22, 2017 reply Follow Share @nandini Gupta.I assume you have considered both expressions as one while they are not a common expression. (bx)*b means any number of bx first then b. But bx in pair not xb and bx. here it's not b*x* it's (bx)* repeation will be in pairr only. 0 votes 0 votes bhargav9873 commented Feb 13, 2017 reply Follow Share @nandini None on the expressions can derive bbxxb The only string they can derive is bxbxbxbxb.... 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Yes they are same by shifting property. Purvi Agrawal answered Feb 2, 2017 Purvi Agrawal comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Both Regelar expressions are equivalent The language derived is a bxbxbxbxb...... In 1st case u r focusing on the 1st 'b' recursing the rest Where as in 2nd case u are focusing on last 'b' recursing what's ahead of it But ultimately both derive the same language This is a good example to show that regular expression being non deterministic in nature can have more than 1 regular expressions for the same language bhargav9873 answered Feb 13, 2017 bhargav9873 comment Share Follow See all 0 reply Please log in or register to add a comment.