pumping lemmas

views updated

pumping lemmas Two theorems in formal language theory that express necessary conditions for languages to be regular or context-free:

If language L is regular, there exists an integer n such that,

for any word z in L, |z|>n,

there exist u,v,w with z = uvw, v nonempty, |vw|←n,

such that: uvkwL, for all k≥0

If language L is context-free, there exist integers p and q such that,

for any z in L, with |z|>p,

there exist u,v,w,x,y with z = uvwxy, v and x nonempty, |vwx|←q,

such that: uvkwxkyL, for all k≥0

The conditions are used in constructing algorithms for decision problems about regular and context-free grammars, and in proving certain languages are not regular or are not context-free.