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

for 1st one dfa possible or not, give enough prove when u challenging one answer

---

Hmmm I think you are right I made some mistake.. I need to cross-check this..

---

Shrestha.. Wait a minute try this string aaaaaaaabbbbbb number of a =8 number of b =6 it should be accepted but your dfa cannot accept it..

---

@vamp

actually when aaa u r taking it is going (3 no of a - 0 no of b)=3

So, it shouldnot be accepted

---

Definitely this is what I m trying to say you don't know how big a can be and what value of b u will take relatively cannot be represented in dfa..

You cannot represent all the possible solutions through this dfa.. As you can see my string is valid still it is not accepted by your dfa.. You can make a dfa as large as possible but I will give you a string that would be valid but cannot be accepted.. I hope the answer would be not regular.. Plz do some digging I want to be sure about it.

---

@vamp

u interpret my comment wrongly

the string is only going to take string which are (no of a - no of b)=2

means difference of a and b cannot go beyond 2

but ur example is wrong

when u taking aaa upto this one,  ur string only goes to beyond range of 2

So, your both example is wrong

---

Cannot an infinite string make a DFA?

I think my ans is correct, as no one can give example violating condition

---

Definitely an infinite string can be represented on finite automata but there has to be a loop on which it is implemented...

In this question try to see.. You are making dfa with restrictions you cannot say my example is wrong as the language given in question my example is definitely right.. The number of a - the number of b<=2 I cannot give example according to your dfa I can give example according to the language..

You try to understand whenever we try to subtract and then check length we are doing comparison.. We have to store infinite a and then relatively infinite b.. Infinite comparison on finite automata is never ever possible.. Plz check your concept once more.. Don't go fast and aggressive.. Give me genuine reason

---

And everytime I m saying that my example is not wrong.. aaaaaaaaaaabbb in this example don't we have number of a and b difference <10 it is appropriate with language given in question.. But you make dfa which cannot accept it.. So how my example is wrong.. Your dfa should be capable of process every string with this language.. If it cannot then definitely dfa is wrong

---

Can u plz explain how will it be ensure that ww^r (Comparison wud be needed or not here)in the L2 part?

I'm very confused here.. Please explain

@vamp_vaibhav

---

 (a+b)* is superset of ww^r ,So when (a+b)* is accepted no need to check ww^r . ^.

---

Atul_21 I am not able to get  your question.. If u don't mind Can you Plz write it clearly....

---

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.