Why pumping lemma for context free languages do not have bound on first part of string?

32 views Asked by At

Pumping lemma for Regular Languages (RLs) states that

For any Regular Language (L) there is a number p such that for any string w in L such that length of w,|w|>=p then there is a partition of w = uvy, where |uv|<=p, |v|>0 so that for every i in whole numbers uv^iy will also be in L.

But in the case of pumping lemma for Context-Free Languages (CFLs)

For any CFL (L) there is a number p such that for any string w in L such that length of w,|w|>=p then there is a partition of w = uvxyz such that length of substring |vxy|<=p, |vy|>0 then for every i in whole numbers, uv^ixy^iz will also be in L

My question is in case of RLs we bounded the starting part of string u by saying that |uv|<=p, but we have no bound on u in case of CFLs why?

0

There are 0 answers