1 votes 1 votes only option C is regular right ? A_i_$_h asked Jan 25, 2018 A_i_$_h 601 views answer comment Share Follow See all 12 Comments See all 12 12 Comments reply hs_yadav commented Jan 25, 2018 reply Follow Share no...both B & C are correct... take some example and see...it is (a+b)* 0 votes 0 votes hs_yadav commented Jan 25, 2018 reply Follow Share @ A_i_$_h but i'm confused with first...why this is not regular.... RE for firat Language must be like this... (a+(bc+)+ isn't it? 0 votes 0 votes Ajay Jadhav commented Jan 25, 2018 reply Follow Share c^k has to be repeated,I think you cant keep track of count of c in next iteration. I dont get how B option is right? 1 votes 1 votes Shubhanshu commented Jan 25, 2018 reply Follow Share Option B) is a complete language over (a,b) and it is one of the famous question from TOC over Gateoverflow. Consider a string aabbaabbaabababa. it is in the Language where # a = # b = 4. Bolded part is x and remaining is of y. 0 votes 0 votes Ajay Jadhav commented Jan 25, 2018 reply Follow Share Can you please provide the link for this question's discussion? 2 votes 2 votes Anjan commented Jan 25, 2018 reply Follow Share Good Question 0 votes 0 votes A_i_$_h commented Jan 27, 2018 reply Follow Share @shubhanshu to check no of a's in x and no of b's in y to be equal we require memory which will make it non regular right? can you explain a bit moe or provide that link of discussion would be helpful 0 votes 0 votes A_i_$_h commented Jan 27, 2018 reply Follow Share what is the string is aaaaaa...(bolded is x ) this is also accepted by the language and here no of a's in x is not equal to number of b's in y 0 votes 0 votes Shubhanshu commented Jan 27, 2018 reply Follow Share This question is discussed previously but I am unable to recollect that link. But I can give you idea. So, the idea is that in any string means ANY string you have to find a partition point where you can divide the given string. For example in your string i.e. aaaaaa..., Now to make # a in x = # b in y, We can divide the string as taking x as EPSILON and y as remaining string which is aaaaaaa.... here. This concludes that #a in x = #b in y = 0. Coming to its DFA, It will be the DFA of complete language. i.e. (a+b)* and you know how to draw its DFA. 1 votes 1 votes A_i_$_h commented Jan 27, 2018 reply Follow Share nice one :) thank you 0 votes 0 votes hs_yadav commented Jan 27, 2018 reply Follow Share @y A_i_$_h why r deciding which is x and which is y.....let machine do it.... for this automata will treat it like this... taking x as NULL and y as aaaaaa(valid according to no a's in x is equal to no of b's in y/// 0 votes 0 votes A_i_$_h commented Jan 27, 2018 reply Follow Share https://gateoverflow.in/464/gate2008-52?show=199916#c199916 in this question ......the minimal string length acccepted by P is 0 and nt 00 ..how are the options valid...please look into this too...and sorry for posting it here... 0 votes 0 votes Please log in or register to add a comment.