Pumping lemma for context-free languages (original) (raw)
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.
| Property | Value | |
|---|---|---|
| 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 | wiki-commons:Special:FilePath/Pumping_lemma_for_context-free_languages.svg?width=300 | |
| dbo:wikiPageExternalLink | https://archive.org/details/introductiontoth00sips | |
| dbo:wikiPageID | 3193758 (xsd:integer) | |
| dbo:wikiPageLength | 10071 (xsd:nonNegativeInteger) | |
| dbo:wikiPageRevisionID | 1094963273 (xsd:integer) | |
| dbo:wikiPageWikiLink | dbc:Lemmas dbr:Ogden's_lemma dbr:Pumping_lemma_for_regular_languages dbr:Context-free_language dbr:Computer_science dbr:Finite_language dbr:Formal_language_theory dbr:Lemma_(mathematics) dbr:Proof_by_contradiction dbr:Pumping_lemma dbc:Formal_languages dbr:Interchange_lemma dbr:Yehoshua_Bar-Hillel dbr:Substring dbr:String_length dbr:File:Pumping_lemma_for_context-free_languages.svg | |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Math dbt:Mvar dbt:Reflist dbt:Formal_languages_and_grammars | |
| dcterms:subject | dbc:Lemmas dbc:Formal_languages | |
| gold:hypernym | dbr:Lemma | |
| rdf:type | yago:WikicatLemmas yago:WikicatMathematicalTheorems yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 yago:Lemma106751833 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 yago:WikicatFormalLanguages | |
| 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 | freebase:Pumping lemma for context-free languages yago-res:Pumping lemma for context-free languages wikidata:Pumping lemma for context-free languages dbpedia-es:Pumping lemma for context-free languages dbpedia-fa:Pumping lemma for context-free languages dbpedia-fr:Pumping lemma for context-free languages dbpedia-he:Pumping lemma for context-free languages dbpedia-hr:Pumping lemma for context-free languages dbpedia-it:Pumping lemma for context-free languages dbpedia-ja:Pumping lemma for context-free languages dbpedia-mk:Pumping lemma for context-free languages dbpedia-nn:Pumping lemma for context-free languages dbpedia-no:Pumping lemma for context-free languages dbpedia-pl:Pumping lemma for context-free languages dbpedia-pt:Pumping lemma for context-free languages dbpedia-ru:Pumping lemma for context-free languages https://global.dbpedia.org/id/2SLvL | |
| prov:wasDerivedFrom | wikipedia-en:Pumping_lemma_for_context-free_languages?oldid=1094963273&ns=0 | |
| foaf:depiction | wiki-commons:Special:FilePath/Pumping_lemma_for_context-free_languages.svg | |
| foaf:isPrimaryTopicOf | wikipedia-en:Pumping_lemma_for_context-free_languages | |
| is dbo:knownFor of | dbr:Eli_Shamir dbr:Micha_Perles | |
| is dbo:wikiPageRedirects of | dbr:Bar-Hillel_lemma dbr:The_bar-hilel_lemma dbr:The_bar-hillel_lemma dbr:The_bar_Hillel_lemma dbr:The_bar_hilel_lemma dbr:Pumping_lemma_(context-free_languages) dbr:Pumping_lemma_for_context_free_languages | |
| is dbo:wikiPageWikiLink of | dbr:Eli_Shamir dbr:Regular_expression dbr:Index_of_philosophy_articles_(I–Q) dbr:Indexed_grammar dbr:Indexed_language dbr:Induction_of_regular_languages dbr:Computability dbr:Context-free_grammar dbr:Ogden's_lemma dbr:Pumping_lemma_for_regular_languages dbr:Conjunctive_grammar dbr:Context-free_language dbr:Mildly_context-sensitive_grammar_formalism dbr:Micha_Perles dbr:Pattern_language_(formal_languages) dbr:Formal_grammar dbr:Pumping_lemma dbr:Bar-Hillel_lemma dbr:Chomsky_normal_form dbr:The_bar-hilel_lemma dbr:The_bar-hillel_lemma dbr:The_bar_Hillel_lemma dbr:The_bar_hilel_lemma dbr:Interchange_lemma dbr:Noncontracting_grammar dbr:Pumping_lemma_(context-free_languages) dbr:Pumping_lemma_for_context_free_languages | |
| is dbp:knownFor of | dbr:Eli_Shamir dbr:Micha_Perles | |
| is foaf:primaryTopic of | wikipedia-en:Pumping_lemma_for_context-free_languages |
