Pumping lemma: Difference between revisions
Content deleted Content added
Undid revision 636605914 by 122.160.99.86 (talk): markup error |
Kanayejio03 (talk | contribs) No edit summary |
||
| Line 1: | Line 1: | ||
In the theory of [[formal language]]s, the '''pumping lemma''' may refer to |
In the theory of [[formal language]]s, 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 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 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 language#Properties|indexed languages]] |
* [[Pumping lemma]] for [[Indexed language#Properties|indexed languages]] |
||
* Pumping lemma for [[Tree automaton#Pumping Lemma|regular tree languages]] |
* [[Pumping lemma]] for [[Tree automaton#Pumping Lemma|regular tree languages]] |
||
==See also== |
==See also== |
||
* [[Ogden's lemma]], a stronger version of the pumping lemma for context-free languages |
* [[Ogden's lemma]], a stronger version of the [[pumping lemma]] for [[context-free languages]] |
||
{{sia}} |
{{sia}} |
||
Revision as of 05:31, 17 June 2015
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 also
- Ogden's lemma, a stronger version of the pumping lemma for context-free languages
This article includes a list of related items that share the same name (or similar names).
If an internal link incorrectly led you here, you may wish to change the link to point directly to the intended article.
If an internal link incorrectly led you here, you may wish to change the link to point directly to the intended article.