Overview

pumping lemmas


'pumping lemmas' can also refer to...

 

More Like This

Show all results sharing this subject:

  • Computing

GO

Show Summary Details

Quick Reference

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,

z = uvw, v nonempty, |vw|≤n,

uvkw ∈ L, for all k≥0

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.

z = uvwxy, v and x nonempty,

|vwx|≤q,

uvkwxky ∈ L, for all k ≥ 0

Subjects: Computing.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.