| dbpprop:abstract
|
- In the theory of formal languages in computability theory, a pumping lemma states that any string in such a language of at least a certain length (called the pumping length), contains a section that can be removed, or repeated any number of times, with the resulting string remaining in that language. The proofs of these lemmas typically require counting arguments such as the pigeonhole principle. The two most important examples are the pumping lemma for regular languages and the pumping lemma for context-free languages. Ogden's lemma is a second, stronger pumping lemma for context-free languages. These lemmas can be used to determine if a particular language is not in a given language class. However, they cannot be used to determine if a language is in a given class, since satisfying the pumping lemma is a necessary, but not sufficient, condition for class membership.
- Das Pumping-Lemma bzw. Pumplemma (auch Schleifensatz genannt) beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht kontextfrei ist. Seinen Namen hat das Lemma vom englischen Begriff to pump, zu deutsch aufpumpen. Er leitet sich davon ab, dass Teile von Wörtern aus Sprachen bestimmter Klassen vervielfacht (aufgepumpt) werden können, so dass die dabei entstehenden Wörter ebenfalls in der Sprache sind. Man unterscheidet zunächst zwischen dem Pumping-Lemma für reguläre Sprachen und jenem für kontextfreie Sprachen. In der Literatur sind weiterhin Pumping-Lemmata für Erweiterungen der kontextfreien Sprachen anzutreffen. Mächtigere Sprachklassen in der Chomsky-Hierarchie wie die kontextsensitiven Sprachen und auch die wachsend kontextsensitiven Sprachen ermöglichen jedoch kein Pumpinglemma. Alternativ wird das Lemma bzw. seine Ausprägungen auch als uvw-Theorem, uvwxy-Theorem, Schleifenlemma, Iterationslemma oder Lemma von Bar-Hillel bezeichnet.
- V teorii formálních jazyků je lemma o vkládání (pumping lemma) výrok, že každý jazyk z dané třídy jazyků může být „napumpován“: každé dostatečně dlouhé slovo v daném jazyce může být rozděleno na části, jejichž zopakováním lze získat opět nějaké slovo z jazyka. To znamená, že pokud pro danou třídu jazyků existuje lemma o vkládání, každý jazyk v této třídě, který není konečný, bude obsahovat nekonečně mnoho slov vyprodukovatelných jednoduchým pravidlem daným tímto lemmatem (v případě konečných jazyků lze onu „dostatečnou délku slova“ nastavit na více, než je délka nejdelšího slova v jazyce). Dvě nejdůležitější lemmata o vkládání jsou lemmata pro regulární jazyky a pro bezkontextové jazyky. Obě tato lemmata se využívají k důkazu skutečnosti, že jazyk neleží v dané třídě, nemohou být použity k důkazu toho, že jazyk v dané třídě leží. Lemma o vkládání je totiž podmínkou nutnou, nikoliv postačující.
- En la teoría de lenguajes formales de la teoría de la computabilidad, un lema de bombeo establece que en un lenguaje, cualquier cadena de caracteres de por lo menos una cierta longitud (llamada longitud de bombeo), contiene una sección que puede ser removida o repetida cualquier número de veces, con la cadena resultante permaneciendo en ese lenguaje. La prueba de este lema típicamente requiere argumentos de conteo como los del principio del palomar. Los dos más importantes ejemplos son el lema del bombeo para lenguajes regulares y el lema del bombeo para lenguajes libre de contexto. El lema de Ogden es un segundo, más fuerte, lema de bombeo para lenguajes libres de contexto. Estos lemas pueden ser usados para determinar si un lenguaje no está en una clase de lenguajes. Sin embargo, no pueden ser usados para determinar si un lenguaje está en una clase, puesto que satisfacer el lema del bombeo es una necesaria, pero no una suficiente condición, para ser miembro de una clase.
- En théorie des langages, le lemme de l'étoile (ou encore lemme d'itération, lemme de pompage, pumping lemma en anglais) décrit une propriété essentielle de tout langage rationnel. Informellement, il établit que tout mot suffisamment long d'un langage rationnel peut être pompé, c'est-à-dire qu'une partie centrale du mot peut être répétée un nombre arbitraire de fois pour produire un nouveau mot qui se trouve encore dans le langage initial. Le lemme de l'étoile a été imaginé pour la première fois par Y. Bar-Hillel, M. Perles, E. Shamir en 1961. Il est très pratique pour montrer qu'un langage donné n'est pas rationnel (en raisonnant par l'absurde).
- Il lemma pumping o lemma del pompaggio riguarda la presenza in ogni linguaggio context-free infinito (e in particolare in ogni linguaggio regolare infinito) di successioni di stringhe che presentano regolarità ben definite. In particolare ogni stringa sufficientemente lunga di un tale linguaggio contiene una o due porzioni che possono essere ripetute un numero arbitrario di volte ottenendo ancora una stringa appartenente al linguaggio. Il pumping lemma fornisce una condizione necessaria ma non sufficiente affiché un linguaggio sia regolare o context-free. Può essere utilizzato per determinare che un particolare linguaggio non è in una di queste classi, verificando che il linguaggio non soddisfi la condizione necessaria fornita dal pumping lemma.
- 反復補題（英: Pumping lemma）とは、計算可能性理論において、あるクラスの形式言語に反復を施してもそのクラスに依然として属することを示すものである。ここでいう「反復」とは、その言語に含まれる十分に長い文字列が部分に分割可能で、その一部分を繰り返したさらに長い文字列も同じ言語に含まれるようにすることである。この補題の証明には、鳩の巣原理のような組合せ数学が必要とされる。 反復補題の重要な具体例として、正規言語の反復補題と文脈自由言語の反復補題がある。文脈自由言語の反復補題の一種として、オグデンの補題もある。 これらの補題は、ある言語が特定の言語クラスに属さないことを示すのに使われる。しかし逆に、反復補題を満たすことは必要条件ではあっても十分条件ではないので、ある言語があるクラスに属することを示すのには使えない。
- Het pumping lemma is een begrip uit de studie der formele talen, een onderdeel van de theoretische informatica. Aan de hand van het lemma kan bewezen worden dat een taal niet tot een bepaalde klasse van talen behoort. Het omgekeerde is echter niet waar, als het bewijs faalt betekent dit niet noodzakelijk dat de taal tot de klasse behoort. Het lemma is dus een eigenschap die nodig is om tot een klasse van talen te behoren, maar er niet voldoende uitsluitsel over geeft. De werking van het lemma is er op gebaseerd dat alle woorden in de taal die lang genoeg zijn opgebroken kunnen worden in deelwoorden, waarvan er bepaalde gepompt kunnen worden zodat alle resulterende woorden ook tot de taal behoren. Dit betekent dat die bepaalde deelwoorden weggelaten of een onbepaald aantal keren herhaald kunnen worden, wat men pompen noemt. De belangrijkste voorbeelden van pumping lemma's zijn de volgende: Pumping lemma voor reguliere talen Pumping lemma voor contextvrije talen Ogden's lemma
- Na teoria da linguagens formais na teoria da computabilidade, o lema do bombeamento ou lema da bombagem diz que qualquer linguagem infinita de dada classe pode ser "bombeada" (pumped) e ainda pertencer àquela classe (as linguagens finitas são todas regulares). A linguagem pode ser bombeada se qualquer cadeia suficientemente longa na linguagem pode ser quebrada em pedaços, alguns dos quais podem ser repetidos um número arbitrário de vezes para produzir uma cadeia mais longa na linguagem. Por outras palavras, o acto de repetir a dita subcadeia, não faz com que a palavra "resultante" dessa repetição saia da linguagem. As provas desses lemas tipicamente requerem combinatória tal qual o princípio da casa dos pombos. Os dois exemplos mais importantes são lema do bomeamento para linguagens regulares e o lema do bombeamento para linguagens de livre-contexto . Lema de Ogden é o segundo maior lema do bombeamento para linguagens de livre-contexto. Estes lema podem ser usados para determinar se uma linguagem qualquer não é dada classe de linguagem. No entanto, elas não podem ser usadas para determinar se uma linguagem está em dada classe, já que satisfazer o lema do bombeamento é uma condição necessária, mas não suficiente, para se fazer parte da classe.
- În teoria limbajelor formale, o lemă de pompare spune că orice limbaj dintr-o clasă dată, dacă este "pompat", rămâne neschimbat. Pomparea unui limbaj presupune ca orice şir suficient de lung din limbaj să poată fi împărţit în componente, a căror repetare produce alte şiruri, care vor face parte toate din limbajul respectiv. Astfel, dacă există o lemă de pompare pentru o clasă dată de limbaje, majoritatea limbajelor din acea clasă va conţine o mulţime infinită de şiruri finite, toate produse prin regula simplă dată de lemă. În general, asemenea rezultate depind de principiul lui Dirichlet.
- Лемма о накачке, или лемма о разрастании - в теории автоматов важная лемма, позволяющая во многих случаях проверить, является ли данный язык автоматным. Поскольку все конечные языки являются автоматными, эту проверку имеет смысл делать только для бесконечных языков. Существует также лемма о разрастании для контекстно-свободных языков. Термин «накачка» в названии леммы отражает возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка.
- 在可计算性理论中的形式语言理论中，泵引理声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸，如果在这个语言中任何足够长的字符串可以分解成片段，其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要计数论证比如鸽笼原理。 两个最重要例子是正则语言的泵引理和上下文无关语言的泵引理。Ogden引理是另一种更强的上下文无关语言的泵引理。 这些引理可以用来确定特定语言不在给定语言类中。但是它们不能被用来确定一个语言在给定类中，因为满足引理是类成员关系的必要条件，但不是充分条件。 泵引理是1961年由 Y. Bar-Hillel、M. Perles 和 E. Shamir 首次发表的。
|
| rdfs:comment
|
- In the theory of formal languages in computability theory, a pumping lemma states that any string in such a language of at least a certain length (called the pumping length), contains a section that can be removed, or repeated any number of times, with the resulting string remaining in that language. The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.
- Das Pumping-Lemma bzw. Pumplemma (auch Schleifensatz genannt) beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht kontextfrei ist. Seinen Namen hat das Lemma vom englischen Begriff to pump, zu deutsch aufpumpen.
- V teorii formálních jazyků je lemma o vkládání (pumping lemma) výrok, že každý jazyk z dané třídy jazyků může být „napumpován“: každé dostatečně dlouhé slovo v daném jazyce může být rozděleno na části, jejichž zopakováním lze získat opět nějaké slovo z jazyka.
- En la teoría de lenguajes formales de la teoría de la computabilidad, un lema de bombeo establece que en un lenguaje, cualquier cadena de caracteres de por lo menos una cierta longitud (llamada longitud de bombeo), contiene una sección que puede ser removida o repetida cualquier número de veces, con la cadena resultante permaneciendo en ese lenguaje. La prueba de este lema típicamente requiere argumentos de conteo como los del principio del palomar.
- En théorie des langages, le lemme de l'étoile (ou encore lemme d'itération, lemme de pompage, pumping lemma en anglais) décrit une propriété essentielle de tout langage rationnel. Informellement, il établit que tout mot suffisamment long d'un langage rationnel peut être pompé, c'est-à-dire qu'une partie centrale du mot peut être répétée un nombre arbitraire de fois pour produire un nouveau mot qui se trouve encore dans le langage initial.
- Il lemma pumping o lemma del pompaggio riguarda la presenza in ogni linguaggio context-free infinito (e in particolare in ogni linguaggio regolare infinito) di successioni di stringhe che presentano regolarità ben definite. In particolare ogni stringa sufficientemente lunga di un tale linguaggio contiene una o due porzioni che possono essere ripetute un numero arbitrario di volte ottenendo ancora una stringa appartenente al linguaggio.
- Het pumping lemma is een begrip uit de studie der formele talen, een onderdeel van de theoretische informatica. Aan de hand van het lemma kan bewezen worden dat een taal niet tot een bepaalde klasse van talen behoort. Het omgekeerde is echter niet waar, als het bewijs faalt betekent dit niet noodzakelijk dat de taal tot de klasse behoort. Het lemma is dus een eigenschap die nodig is om tot een klasse van talen te behoren, maar er niet voldoende uitsluitsel over geeft.
- Na teoria da linguagens formais na teoria da computabilidade, o lema do bombeamento ou lema da bombagem diz que qualquer linguagem infinita de dada classe pode ser "bombeada" (pumped) e ainda pertencer àquela classe (as linguagens finitas são todas regulares). A linguagem pode ser bombeada se qualquer cadeia suficientemente longa na linguagem pode ser quebrada em pedaços, alguns dos quais podem ser repetidos um número arbitrário de vezes para produzir uma cadeia mais longa na linguagem.
- În teoria limbajelor formale, o lemă de pompare spune că orice limbaj dintr-o clasă dată, dacă este "pompat", rămâne neschimbat. Pomparea unui limbaj presupune ca orice şir suficient de lung din limbaj să poată fi împărţit în componente, a căror repetare produce alte şiruri, care vor face parte toate din limbajul respectiv.
- Лемма о накачке, или лемма о разрастании - в теории автоматов важная лемма, позволяющая во многих случаях проверить, является ли данный язык автоматным. Поскольку все конечные языки являются автоматными, эту проверку имеет смысл делать только для бесконечных языков.
|
![[RDF Data]](/statics/sw-cube.png)
