| dbo:abstract
|
- En ciencia de la computación, en particular en la teoría de lenguajes formales, el lema del bombeo para lenguajes libres del contexto, también conocido como lema de Bar-Hille, es un lema que brinda una propiedad compartida por todos los lenguajes libres del contexto y generaliza el lema del bombeo para lenguajes regulares. Como el lema del bombeo no garantiza que el lenguaje sea libre del contexto, existen condiciones necesarias más fuertes, como el lema de Ogden. (es)
- Le lemme d'itération pour les langages algébriques, aussi connu sous le vocable lemme de Bar-Hillel, Perles et Shamir, donne une condition de répétition nécessaire pour les langages algébriques. Sa version simplifiée pour les langages rationnels est le lemme de l'étoile. Une version plus élaborée du lemme d'itération est le lemme d'Ogden. (fr)
- In computer science, in particular in formal language theory, the pumping lemma for context-free languages, also known as the Bar-Hillel lemma, is a lemma that gives a property shared by all context-free languages and generalizes the pumping lemma for regular languages. The pumping lemma can be used to construct a proof by contradiction that a specific language is not context-free. Conversely, the pumping lemma does not suffice to guarantee that a language is context-free; there are other necessary conditions, such as Ogden's lemma, or the Interchange lemma. (en)
- 文脈自由言語の反復補題（ぶんみゃくじゆうげんごのはんぷくほだい、英: Pumping lemma for context-free languages）は、全ての文脈自由言語が持つ属性を与える反復補題である。Bar-Hillelの補題や、uvwxy定理とも呼ばれる。その主たる用法は、ある言語が文脈自由言語でないことを証明することである。 文脈自由言語の反復補題は、任意の文脈自由言語でない言語が文脈自由でないことを証明するのに使えるわけではない。場合によってはより汎用化されたオグデンの補題を使う必要がある。 (ja)
- Il pumping lemma per i linguaggi liberi dal contesto, detto anche lemma di Bar-Hillel, è un lemma che fornisce una proprietà comune a tutti i linguaggi liberi dal contesto. Poiché descrive una condizione necessaria per l'appartenenza di un linguaggio alla classe dei linguaggi liberi dal contesto, viene tipicamente utilizzato per dimostrare che un certo linguaggio non è context-free. (it)
- Lemat o pompowaniu dla języków bezkontekstowych to twierdzenie służące do udowadniania, że dany język nie jest bezkontekstowy. Jego uogólnieniem jest lemat Ogdena. (pl)
- O lema do bombeamento para linguagens livres de contexto, também conhecido como o lema Bar-Hillel, é um lema que que sua propriedade é compartilhada por todas as linguagens livres de contexto.Declaração FormalSe uma linguagem L é livre de contexto, então existe algum inteiro p ≥ 1 tal que qualquer cadeia s em L com | s | ≥ p (onde p é um "comprimento de bombeamento") pode ser escrita como (pt)
- Лемма о разрастании для контекстно-свободных языков — лемма, по аналогии с одноименной леммой для регулярных языков позволяющая относительно несложно доказывать, что данный язык не является контекстно-свободным. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10071 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En ciencia de la computación, en particular en la teoría de lenguajes formales, el lema del bombeo para lenguajes libres del contexto, también conocido como lema de Bar-Hille, es un lema que brinda una propiedad compartida por todos los lenguajes libres del contexto y generaliza el lema del bombeo para lenguajes regulares. Como el lema del bombeo no garantiza que el lenguaje sea libre del contexto, existen condiciones necesarias más fuertes, como el lema de Ogden. (es)
- Le lemme d'itération pour les langages algébriques, aussi connu sous le vocable lemme de Bar-Hillel, Perles et Shamir, donne une condition de répétition nécessaire pour les langages algébriques. Sa version simplifiée pour les langages rationnels est le lemme de l'étoile. Une version plus élaborée du lemme d'itération est le lemme d'Ogden. (fr)
- In computer science, in particular in formal language theory, the pumping lemma for context-free languages, also known as the Bar-Hillel lemma, is a lemma that gives a property shared by all context-free languages and generalizes the pumping lemma for regular languages. The pumping lemma can be used to construct a proof by contradiction that a specific language is not context-free. Conversely, the pumping lemma does not suffice to guarantee that a language is context-free; there are other necessary conditions, such as Ogden's lemma, or the Interchange lemma. (en)
- 文脈自由言語の反復補題（ぶんみゃくじゆうげんごのはんぷくほだい、英: Pumping lemma for context-free languages）は、全ての文脈自由言語が持つ属性を与える反復補題である。Bar-Hillelの補題や、uvwxy定理とも呼ばれる。その主たる用法は、ある言語が文脈自由言語でないことを証明することである。 文脈自由言語の反復補題は、任意の文脈自由言語でない言語が文脈自由でないことを証明するのに使えるわけではない。場合によってはより汎用化されたオグデンの補題を使う必要がある。 (ja)
- Il pumping lemma per i linguaggi liberi dal contesto, detto anche lemma di Bar-Hillel, è un lemma che fornisce una proprietà comune a tutti i linguaggi liberi dal contesto. Poiché descrive una condizione necessaria per l'appartenenza di un linguaggio alla classe dei linguaggi liberi dal contesto, viene tipicamente utilizzato per dimostrare che un certo linguaggio non è context-free. (it)
- Lemat o pompowaniu dla języków bezkontekstowych to twierdzenie służące do udowadniania, że dany język nie jest bezkontekstowy. Jego uogólnieniem jest lemat Ogdena. (pl)
- O lema do bombeamento para linguagens livres de contexto, também conhecido como o lema Bar-Hillel, é um lema que que sua propriedade é compartilhada por todas as linguagens livres de contexto.Declaração FormalSe uma linguagem L é livre de contexto, então existe algum inteiro p ≥ 1 tal que qualquer cadeia s em L com | s | ≥ p (onde p é um "comprimento de bombeamento") pode ser escrita como (pt)
- Лемма о разрастании для контекстно-свободных языков — лемма, по аналогии с одноименной леммой для регулярных языков позволяющая относительно несложно доказывать, что данный язык не является контекстно-свободным. (ru)
|
| rdfs:label
|
- Lema del bombeo para lenguajes libres del contexto (es)
- Lemme d'itération pour les langages algébriques (fr)
- Pumping lemma per i linguaggi liberi dal contesto (it)
- 文脈自由言語の反復補題 (ja)
- Pumping lemma for context-free languages (en)
- Lemat o pompowaniu dla języków bezkontekstowych (pl)
- Lema do bombeamento para linguagens livre de contexto (pt)
- Лемма о разрастании для контекстно-свободных языков (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
