2 votes 2 votes is it equal?? $(a^{+}b^{+})^*$= $(a^{+}b)^*(ab^{+})^*$ Theory of Computation theory-of-computation + – focus _GATE asked Jan 10, 2017 • edited Jan 10, 2017 by srestha focus _GATE 671 views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply srestha commented Jan 10, 2017 reply Follow Share RHS it is possible $aaba$ from 1st half it is not possible for LHS 0 votes 0 votes focus _GATE commented Jan 10, 2017 reply Follow Share means not equal na ?? 0 votes 0 votes Pratyush Madhukar commented Jan 10, 2017 reply Follow Share @Srestha: Are you sure string $aaba$ is possible from RHS? 0 votes 0 votes srestha commented Jan 10, 2017 reply Follow Share yes not equal ($(a^{+}b)^*$)=($(a^{+}b)^*(a^{+}b)^*$) taking aab from 1st one ,a from 2nd one 0 votes 0 votes Pratyush Madhukar commented Jan 10, 2017 reply Follow Share $(a^+ b)^* (a^+b)^*$ if you take an $a$ from 2nd one, you have to take a $b$ as well. There is no $*$ over $b$, so it must be included once (and only once for each term $(a^+b)$). 0 votes 0 votes srestha commented Jan 10, 2017 reply Follow Share No b* can take even $\epsilon$ 0 votes 0 votes Pratyush Madhukar commented Jan 10, 2017 i edited by Pratyush Madhukar Jan 10, 2017 reply Follow Share But is $b^*$ there? It's $(a^+b)^*$. So you can replace the whole term by $\epsilon$ but not individual b. Either you choose $\epsilon$ from $(a^+b)^*$ or, if you choose anything, you must choose at least one $a$ followed by exactly one $b$, for each $(a^+b)$ you consider. 0 votes 0 votes srestha commented Jan 10, 2017 reply Follow Share No, it is not (a+b)* where * means you may take string (a+b) or not Now (a+b) means when u taking a string u must take atleast one a. https://gateoverflow.in/27552/dfa-for-wxwr-w-x-belong-to-a-b this question may u help more 0 votes 0 votes srestha commented Jan 11, 2017 reply Follow Share yes @pratyush madhukar u r right. Then both LHS=RHS 1 votes 1 votes Please log in or register to add a comment.