How is the Pumping Lemma used to show that b cannot be accepted by an FA?
The question is from Introduction to Languages and the Theory of Computation 4th by John C. Martin.
do your own homework, Pajeet
>>54915748
Not Pajeet.
This is why Pajeets should avoid university and just stick to Java.
>>54915748
>>54915768
I am European. Can you recommend other forums that are better suited for these type of questions?
>>54915739
This is why CS is a bullshit degree.
It's just a bunch of jargon and symbols to dress up ideas that can be explained and reasoned intuitively in plain language.
>>54915890
sour grapes make the best whine
>>54915739
Condition three is not satisfied, I guess.
>>54915739
Fuck I did this in a module like a month ago, forgot it all already though.
>>54916165
The examples in the textbook are inadequate in explaining this particular problem.
>>54915739
I got an a in ToC last semester and I can answer this question. Post picture of your tits for answer.
>>54915795
stackexchange / cs
>>54916407
Thanks
>>54915739
Right here buddy. Just follow my instructions.
>>54916610
Your fingers are so fucking gay
>>54916657
Well they have been inside other men's asses though I'm not sure it reflects poorly on them.
>>54916610
How did you become so autistic?
>>54916693
I think this video explains it :(
https://youtu.be/wV1FrqwZyKw
>>54916690
>they have been inside other men's asses
/pol/ was right about your kind.
>>54916746
Mathematicians?
>>54916768
degenerates
>>54916788
Degenerate faggot with a background in computational mathematics.
The request stands.
>>54916831
>The request stands
?
>>54916862
Oh I'll post the answer to his homework for a pic of op's tits.
With a timestamp of course.
That was what was behind my faggy fingers.
>>54916894
>op's tits.
There is a 0.001 chance that OP has tits.
>>54916948
Are you including man-tits in that calculation?
Also I don't care. It's not about arousal it's about the prostration.
>>54916610
related: know any good ebooks on this subject?
>>54916980
Sipser's was good. Brookshear is what we used in my class. They were both good in different places but the quality only depended upon whether the explanation clicked with me.
>>54916980
OP here. We don't use this book but it's a free light-weight pdf:
http://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf
>>54917039
>http://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf
>>54917034
thanks guys, been needing some summer reading material for a bit.
>>54915739
Take a word x from L.
Then x=(a^i)(b^j)(a^k), for some fixed i,j,k.
If we choose a^i=u, b^j=v, a^k=w, and n=i+j, then
x=uvw. From the lemma, the word y=u(v^i')w also belongs in L, for every i'. Which means
y=(a^i)[(b^j)^i']a^k belongs in L for every i'.
Choosing i'=k, we get
y=(a^i)(b^jk)(a^k) belongs in L.
By the definition of L, we want the sum of the first two exponents to be smaller than the third, i.e. i+jk<k, which is obviously not true, aka we got into a contradiction.
We assumed L is regular, and then using the lemma, we got a contradiction. Therefore, L is not regular.
The whole idea is to take a word x=uvw from L and then using a lemma, this forces a "derivative" word y=u(v^i')w to be in L as well. Then you choose appropriate i' such that the condition to belong in L is not satisfied, getting a contradiction.
There are no books for that, just practice with examples and check solved exercises.
Also take my "solution" with a huge grain of salt, I did automata in my first year and it's been a long time since.
>>54917649
Killjoy
>>54917649
You made an error at this line
>if we choose a^i=u...
The pumping lemma states that for each x in L, there exist u,v,w satisfying the constraint specified. It did not say you can arbitrarily choose u,v,w
>>54917764
true, true, into the garbage it goes I guess..
>>54917831
Don't be crestfallen. It's very close besides the whole being completely wrong.
>>54916980
/sci/ here. Try this text.
http://math.tut.fi/~ruohonen/FL.pdf
>>54917984
This? Damn I'm getting worse by the day.
x=uvw in L => u=(a^i')(b^j'), v=(b^j'')(a^k'), w=(a^k''), with i'+j'+j'' < k'+k''. This is the only form u,v,w can take because of the structure of L, you need all a's adjacent to b's.
Then y=u(v^m)v also in g for every m.
=> (a^i')(b^j')[(b^j'')(a^k')]^m (a^k'') also in L, that is
(a^i')(b^[j'+mj''])(a^[mk'+k'']) in L.
=> i'+j'+mj''<mk'+k'' => m(j''-k')<k''-i'-j' => (for j''-k'≠0) m < (k''-i'-j')/(j''-k'), which is false, because i',j',k',j'',k'' are fixed but m can be any m>0.
Therefore contradiction.
>>54918226
Same error you can't just give a counter example. You need to prove there is no way to choose u v w such that those cases work.
>>54918426
I don't think it's a counterexample.
If u,v,w exist such that x=uvw is in L, this kinda restricts the form of u,v,w to the one in my previous post.
Then u(v^m)w has a specific form, and it's also in L. But this form doesn't satisfy the condition of L ==> contradiction.
Therefore no such u,v,w exist ==> L not regular.
>>54918226
Probably correct, but your choice of variables is retarded and makes it fucking hard to read.
