 |
Pumping lemma
| English Wikipedia - The Free Encyclopedia | Download this dictionary |
Pumping lemma
In the theory of formal languages, the pumping lemma may refer to:
- Pumping lemma for regular languages, the fact that all sufficiently long strings in such a language have a substring that can be repeated arbitrarily many times, usually used to prove that certain languages are not regular
- Pumping lemma for context-free languages, the fact that all sufficiently long strings in such a language have a pair of substrings that can be repeated arbitrarily many times, usually used to prove that certain languages are not context-free
- Pumping lemma for indexed languages
- Pumping lemma for regular tree languages
| See more at Wikipedia.org... |
© This article uses material from Wikipedia® and is licensed under the GNU Free Documentation License and under the Creative Commons Attribution-ShareAlike License
