28 votes 28 votes Which one of the following regular expressions is NOT equivalent to the regular expression $(a + b + c)^*$? $(a^* + b^* + c^*)^*$ $(a^*b^*c^*)^*$ $((ab)^* + c^*)^*$ $(a^*b^* + c^*)^*$ Theory of Computation gateit-2004 theory-of-computation regular-expression normal + – Ishrat Jahan asked Nov 1, 2014 • edited Mar 3, 2018 by kenzou Ishrat Jahan 8.9k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply rajan commented Dec 2, 2016 i edited by rajan Dec 28, 2016 reply Follow Share option c can never form 'a' but our question expression will be 8 votes 8 votes set2018 commented Oct 25, 2017 reply Follow Share how option d generate (a+b+c)* 0 votes 0 votes Nirmal Gaur commented Jan 13, 2020 reply Follow Share If r is a regular expression denoting a language L(r) over some alphabet Σ, and we have Σ ⊆ L(r) then L((r)*) = Σ*. Source: http://www.fbeedle.com/formallanguage/ch07.pdf 0 votes 0 votes smsubham commented Mar 8, 2020 reply Follow Share C is forcing us to have a and b together, so we cannot have only a or b. 1 votes 1 votes Please log in or register to add a comment.
Best answer 46 votes 46 votes $(a^* + b^\ast + c^\ast)^\ast = ( \epsilon + a+aa+ \ldots +b+bb+\ldots +c+cc + \ldots)^\ast = (a+b+c+ aa+\ldots + bb +\ldots +cc+\ldots )^\ast= (a+b+c)^\ast$ [any combination of rest of $aa ,bb,cc,$ etc. already come in $(a+b+c)^\ast$ ] $(a^\ast b^\ast c^\ast)^\ast = (a^\ast+b^\ast+c^\ast +a^\ast b^\ast+b^\ast c^\ast+a^\ast c^\ast+ \ldots)^\ast=(a+b+c+\ldots)^\ast = (a+b+c)^\ast$ $((ab)^\ast + c^\ast)^\ast =(ab+c+\epsilon +abab+\ldots)^\ast = (ab+c)^\ast$ $(a^\ast b^\ast + c^\ast)^\ast = (a^\ast+b^\ast+c^\ast+\ldots)^\ast =(a+b+c+\ldots)^\ast =(a+b+c)^\ast$ Correct Answer: C. Praveen Saini answered Mar 2, 2015 • edited Jun 2, 2021 by Lakshman Bhaiya Praveen Saini comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Praveen Saini commented Nov 24, 2017 reply Follow Share $(a+b + more\:strings\:from \:combinations\: of\: \{a,b\})^* = (a+b)^*$ eg: $(a+b+ab)^*= (a+b)^*$ 7 votes 7 votes ayushsomani commented Dec 5, 2019 reply Follow Share @Praveen Saini @abhishekmehta4u Can we say $a^{*}b^{*}$ = $a^{*}+b^{*}$? 0 votes 0 votes Anwesha_Mishra commented Jun 3, 2020 reply Follow Share We can't say that. For ex. a*b* can generate ab but a* + b* can't generate it. 2 votes 2 votes Please log in or register to add a comment.
11 votes 11 votes ((ab)* + c*)* will not produce the strings where 'a' comes without 'b' and vice-versa. Therefore, language generated by option (c) is proper subset of language genrated by (a+b+c)* . Answer would be (C). suraj answered Dec 2, 2014 suraj comment Share Follow See all 0 reply Please log in or register to add a comment.
9 votes 9 votes Alone string 'a' or string 'b' can't produce by Option C So Option C is Ans. Rajesh Pradhan answered Dec 12, 2016 Rajesh Pradhan comment Share Follow See 1 comment See all 1 1 comment reply Sanjeev kumar Sen commented Aug 15, 2021 reply Follow Share best ans 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes We try to genrate string a,b,c . For each expression . abhishekmehta4u answered Feb 25, 2019 abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.