pumping lemmas
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: uvkw ∈ L, 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: uvkwxky ∈ L, 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.
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: uvkw ∈ L, 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: uvkwxky ∈ L, 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.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
pumping lemmas