CS Theory: Pumping Lemma for Regular Language

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.

Other urls found in this thread:

youtu.be/wV1FrqwZyKw
cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf
math.tut.fi/~ruohonen/FL.pdf
twitter.com/SFWRedditVideos

do your own homework, Pajeet

Not Pajeet.

This is why Pajeets should avoid university and just stick to Java.

I am European. Can you recommend other forums that are better suited for these type of questions?

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.

sour grapes make the best whine

Condition three is not satisfied, I guess.

kek

Fuck I did this in a module like a month ago, forgot it all already though.

The examples in the textbook are inadequate in explaining this particular problem.

I got an a in ToC last semester and I can answer this question. Post picture of your tits for answer.

stackexchange / cs

Thanks

Right here buddy. Just follow my instructions.

Your fingers are so fucking gay

Well they have been inside other men's asses though I'm not sure it reflects poorly on them.

How did you become so autistic?

I think this video explains it :(
youtu.be/wV1FrqwZyKw

>they have been inside other men's asses

Sup Forums was right about your kind.

Mathematicians?

degenerates

Degenerate faggot with a background in computational mathematics.
The request stands.

>The request stands

?

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.

>op's tits.

There is a 0.001 chance that OP has tits.

Are you including man-tits in that calculation?

Also I don't care. It's not about arousal it's about the prostration.

related: know any good ebooks on this subject?

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.

OP here. We don't use this book but it's a free light-weight pdf:

cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf

>cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf
thanks guys, been needing some summer reading material for a bit.

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

Killjoy

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

true, true, into the garbage it goes I guess..

Don't be crestfallen. It's very close besides the whole being completely wrong.

/sci/ here. Try this text.
math.tut.fi/~ruohonen/FL.pdf

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''

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.

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.

Probably correct, but your choice of variables is retarded and makes it fucking hard to read.