| dbo:abstract
|
- 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í. (cs)
- 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. Es 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 Pumping-Lemma. Alternativ wird das Lemma bzw. seine Ausprägungen auch als uvw-Theorem, uvwxy-Theorem, Schleifenlemma, Iterationslemma oder Lemma von Bar-Hillel bezeichnet. (de)
- En la teoría de lenguajes formales de la teoría de la computación, el 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 eliminada o repetida cualquier número de veces, con la cadena resultante perteneciendo a ese lenguaje. La prueba de este lema típicamente requiere argumentos de conteo como los del principio del palomar. Los dos ejemplos más importantes son el lema de bombeo para lenguajes regulares y el lema del bombeo para gramáticas independientes del contexto. El es un segundo lema de bombeo, más fuerte, para . 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 condición necesaria, pero no una suficiente, para ser miembro de una clase. (es)
- En informatique théorique, et spécialement en théorie des langages, un lemme d'itération (pumping lemma en anglais) est un énoncé qui stipule que, dans un langage formel d'une classe particulière, tout mot assez long du langage possède un ou des facteurs qui peuvent être enlevés ou répétés, séparément ou de concert, tout en restant à l'intérieur du langage. Les preuves de ces lemmes utilisent, comme argument de base, le principe des tiroirs. Les principaux résultats sont :
* Lemme d'itération pour les langages rationnels
* Lemme d'itération pour les langages algébriques
* Lemme d'itération pour les langages linéaires
* Lemme d'itération pour les langages indexés
* Lemme d'itération pour les langages réguliers d'arbres
* Lemme d'itération pour les automates quantiques Les plus importants sont le lemme de l'étoile pour les langages rationnels et le lemme d'itération pour les langages algébriques, parfois appelé improprement le lemme de la double étoile. Le lemme d'Ogden est une version plus forte du lemme d'itération pour les langages algébriques. Ces lemmes sont utilisés pour prouver qu'un langage particulier n'est pas dans la classe de langage considérée. Ils ne peuvent pas être utilisés pour vérifier qu'un langage est dans la classe donnée, puisque le lemme ne donne qu'une condition nécessaire, mais pas suffisante d'appartenance. (fr)
- 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 (en)
- Il pumping lemma 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 più 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 affinché un linguaggio sia regolare o context-free, quindi può essere utilizzato per determinare che un particolare linguaggio non sia in una di queste classi, verificando che il linguaggio non soddisfi la condizione necessaria fornita dal pumping lemma. (it)
- 펌핑 보조정리(pumping lemma)는 형식 언어 이론에서 특정 종류 언어의 속성을 나타내주는 보조정리이다. 대표적으로 정규 언어에 대한 것과 문맥 자유 언어에 관한 것 두 가지가 있다. L이 어떤 형식 언어에 속한다면 그 언어에 해당하는 보조정리가 성립하지만, 그 역은 성립하지 않는다. 다시 말해, 펌핑 보조정리는 어떤 L이 특정 형식 언어에 속하기 위한 필요조건이지 충분조건은 아니다. 하지만, 주어진 언어가 특정 펌핑 보조정리를 성립시키지 못한다는 것을 보임으로써 그에 해당하는 형식 언어에 속하지 않음을 보일 수는 있다. (ko)
- 反復補題（英: Pumping lemma）とは、計算可能性理論において、あるクラスの形式言語に反復を施してもそのクラスに依然として属することを示すものである。ここでいう「反復」とは、その言語に含まれる十分に長い文字列が部分に分割可能で、その一部分を繰り返したさらに長い文字列も同じ言語に含まれるようにすることである。この補題の証明には、鳩の巣原理のような組合せ数学が必要とされる。 反復補題の重要な具体例として、正規言語の反復補題と文脈自由言語の反復補題がある。文脈自由言語の反復補題の一種として、オグデンの補題もある。 これらの補題は、ある言語が特定の言語クラスに属さないことを示すのに使われる。しかし逆に、反復補題を満たすことは必要条件ではあっても十分条件ではないので、ある言語があるクラスに属することを示すのには使えない。 (ja)
- De pompstelling (ook gekend als pomplemma of pompend lemma) is een stelling 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: niet elke taal die voldoet aan de eigenschappen uit het pomplemma behoort noodzakelijk tot de klasse. Het lemma geeft dus een eigenschap die nodig, maar niet voldoende is om tot een klasse van talen te behoren. 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 sommige 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 pomplemma's zijn de volgende:
* Pomplemma voor reguliere talen
* Pomplemma voor contextvrije talen
* Ogden's lemma (nl)
- Лемма о накачке (лемма о разрастании, лемма-насос; англ. pumping lemma) — важное утверждение теории автоматов, позволяющее во многих случаях проверить, является ли данный язык автоматным. Поскольку все являются автоматными, эту проверку имеет смысл делать только для бесконечных языков. Термин «накачка» в названии леммы отражает возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка. Существует также лемма о разрастании для контекстно-свободных языков, ещё более общее утверждение — . (ru)
- Лема про накачку (англ. pumping lemma) в теоретичній інформатиці описує властивість певних класів формальних мов. В багатьох випадках за допомогою цієї леми можна довести, що певна формальна мова є не регулярною або не . Свою назву лема отримала з англійського дієслова to pump (укр. накачувати).В теорії формальних мов, лема про накачку для певної мови стверджує, що мова належить класу мов, якщо будь-який досить довгий рядок в мові що містить проміжок який може бути вилучений, чи повторений довільну кількість разів, і отриманий в результаті рядок теж належить мові. Доведення цих лем зазвичай комбінаторне, і може використовувати принцип Діріхле. Два найважливіші приклади - лема про накачку для регулярних мов та . - інша, сильніша лема про накачку для контекстно-вільних мов. Ці леми можуть бути використані для визначення чи дана мова не належить даному класу мов, і не можуть використовуватись для доведення факту приналежності мови класу, через те, що лема про накачку є тільки , а не належності класу. (uk)
- Na teoria da linguagens formais na teoria da computabilidade, o lema do bombeamento ou lema da bombagem (em inglês: pumping lemma) 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 bombeamento para linguagens regulares (em inglês: pumping lemma for regular languages) e o lema do bombeamento para linguagens de livre-contexto (em inglês: pumping lemma for context-free languages). Lema de Ogden é o segundo maior lema do bombeamento para linguagem livre de 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. (pt)
- 在可计算性理论中的形式语言理论中，泵引理（Pumping lemma）声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸，如果在这个语言中任何足够长的字符串可以分解成片段，其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要计数论证比如鸽笼原理。 两个最重要例子是正则语言的泵引理和上下文无关语言的泵引理。鄂登引理是另一种更强的上下文无关语言的泵引理。 这些引理可以用来确定特定语言不在给定语言类中。但是它们不能被用来确定一个语言在给定类中，因为满足引理是类成员关系的必要条件，但不是充分条件。 泵引理是1961年由 、 和 首次发表的。 (zh)
|
| rdfs:comment
|
- 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 (en)
- 펌핑 보조정리(pumping lemma)는 형식 언어 이론에서 특정 종류 언어의 속성을 나타내주는 보조정리이다. 대표적으로 정규 언어에 대한 것과 문맥 자유 언어에 관한 것 두 가지가 있다. L이 어떤 형식 언어에 속한다면 그 언어에 해당하는 보조정리가 성립하지만, 그 역은 성립하지 않는다. 다시 말해, 펌핑 보조정리는 어떤 L이 특정 형식 언어에 속하기 위한 필요조건이지 충분조건은 아니다. 하지만, 주어진 언어가 특정 펌핑 보조정리를 성립시키지 못한다는 것을 보임으로써 그에 해당하는 형식 언어에 속하지 않음을 보일 수는 있다. (ko)
- 反復補題（英: Pumping lemma）とは、計算可能性理論において、あるクラスの形式言語に反復を施してもそのクラスに依然として属することを示すものである。ここでいう「反復」とは、その言語に含まれる十分に長い文字列が部分に分割可能で、その一部分を繰り返したさらに長い文字列も同じ言語に含まれるようにすることである。この補題の証明には、鳩の巣原理のような組合せ数学が必要とされる。 反復補題の重要な具体例として、正規言語の反復補題と文脈自由言語の反復補題がある。文脈自由言語の反復補題の一種として、オグデンの補題もある。 これらの補題は、ある言語が特定の言語クラスに属さないことを示すのに使われる。しかし逆に、反復補題を満たすことは必要条件ではあっても十分条件ではないので、ある言語があるクラスに属することを示すのには使えない。 (ja)
- Лемма о накачке (лемма о разрастании, лемма-насос; англ. pumping lemma) — важное утверждение теории автоматов, позволяющее во многих случаях проверить, является ли данный язык автоматным. Поскольку все являются автоматными, эту проверку имеет смысл делать только для бесконечных языков. Термин «накачка» в названии леммы отражает возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка. Существует также лемма о разрастании для контекстно-свободных языков, ещё более общее утверждение — . (ru)
- 在可计算性理论中的形式语言理论中，泵引理（Pumping lemma）声称给定类的任何语言可以被“抽吸”并仍属于这个类。一个语言可以被抽吸，如果在这个语言中任何足够长的字符串可以分解成片段，其中某些可以任意重复来生成语言中更长的字符串。这些引理的证明典型的需要计数论证比如鸽笼原理。 两个最重要例子是正则语言的泵引理和上下文无关语言的泵引理。鄂登引理是另一种更强的上下文无关语言的泵引理。 这些引理可以用来确定特定语言不在给定语言类中。但是它们不能被用来确定一个语言在给定类中，因为满足引理是类成员关系的必要条件，但不是充分条件。 泵引理是1961年由 、 和 首次发表的。 (zh)
- 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). (cs)
- 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. Es 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. (de)
- En la teoría de lenguajes formales de la teoría de la computación, el 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 eliminada o repetida cualquier número de veces, con la cadena resultante perteneciendo a ese lenguaje. La prueba de este lema típicamente requiere argumentos de conteo como los del principio del palomar. (es)
- En informatique théorique, et spécialement en théorie des langages, un lemme d'itération (pumping lemma en anglais) est un énoncé qui stipule que, dans un langage formel d'une classe particulière, tout mot assez long du langage possède un ou des facteurs qui peuvent être enlevés ou répétés, séparément ou de concert, tout en restant à l'intérieur du langage. Les preuves de ces lemmes utilisent, comme argument de base, le principe des tiroirs. Les principaux résultats sont : Le lemme d'Ogden est une version plus forte du lemme d'itération pour les langages algébriques. (fr)
- Il pumping lemma 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 più porzioni che possono essere ripetute un numero arbitrario di volte ottenendo ancora una stringa appartenente al linguaggio. (it)
- De pompstelling (ook gekend als pomplemma of pompend lemma) is een stelling 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: niet elke taal die voldoet aan de eigenschappen uit het pomplemma behoort noodzakelijk tot de klasse. Het lemma geeft dus een eigenschap die nodig, maar niet voldoende is om tot een klasse van talen te behoren. De belangrijkste voorbeelden van pomplemma's zijn de volgende: (nl)
- Na teoria da linguagens formais na teoria da computabilidade, o lema do bombeamento ou lema da bombagem (em inglês: pumping lemma) 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. (pt)
- Лема про накачку (англ. pumping lemma) в теоретичній інформатиці описує властивість певних класів формальних мов. В багатьох випадках за допомогою цієї леми можна довести, що певна формальна мова є не регулярною або не . Два найважливіші приклади - лема про накачку для регулярних мов та . - інша, сильніша лема про накачку для контекстно-вільних мов. Ці леми можуть бути використані для визначення чи дана мова не належить даному класу мов, і не можуть використовуватись для доведення факту приналежності мови класу, через те, що лема про накачку є тільки , а не належності класу. (uk)
|
