Made easy test series

Question

 How L2 is NOT regular and L3 is regular??? 

please explain

Answer 1

#a - #b <=10 there can be infinite number of solutions for this.. Hence not regular bcz finite representation is not possible we can't put something in loop to produce this language...

wcwwR since c belongs to (a, b) * we can expand c in such a way that language looks like starting nd ending with same symbol therefore it is regular language.

Comments

I mean whatever strings r going to b accepted by the L2 (wcww^r ) DFA. . In those strings how will we ensure that the last part of the strings satisfy ww^r is also present

For example: aba what is w and w^r?

Is w=null string always for all the strings???

---

Actually in this type of questions we don't see that how the wwr is exactly going or not.. As you can see there is another value in between c which belongs to (a+b) *.. Now if you have to accept the string you have to accept (a+b) * also.. Nd we know (a+b) * means all the string possible over a and b which also includes wwr.. Nd we have dfa which accept (a+b) * therefore it is regular ..

You can also claim by making dfa which can accept string starting nd ending with same symbol bcz in starting we have w and ending we have wr.. These questions are tricky.. We have to be careful...  if u remove c from language then it won't be regular.. It won't be even cfl it will be csl

---

Thanku so much for this much. U explained it very well

@vamp_vaibhav

Answer 2

#a - #b are less than or equal to 10. that means the difference between a and b must be less than 10 and there infinite number of such finite string possible . So, this is regular

wcww^r is regular when $w=\epsilon$ andc=(a+b)*

as in this case we got all string like $\left \{ \epsilon ,a,b,aa,bb,ab,abb........ \right \}$

Comments

Similarly it also not be accepted

though it is very big one

---

yes @vamp correct

@Leen see we are creating string for every subset and not for every final string

https://gateoverflow.in/992/gate2006-29

---

srestha  Got it.Thank you.