Ogden's lemma (original) (raw)
Ogdens Lemma, benannt nach , ist eine Methode der theoretischen Informatik, mit der gezeigt werden kann, dass eine formale Sprache keine kontextfreie Sprache ist, da sie Eigenschaften beschreibt, die für alle kontextfreien Sprachen gelten müssen. Es liefert somit nur eine notwendige (keine hinreichende) Bedingung für die Klassifikation als kontextfreie Sprache. Ogdens Lemma ist also nicht geeignet um Kontextfreiheit zu beweisen. Das Pumping-Lemma ist ein Spezialfall von Ogdens Lemma.
| Property | Value |
|---|---|
| dbo:abstract | Ogdens Lemma, benannt nach , ist eine Methode der theoretischen Informatik, mit der gezeigt werden kann, dass eine formale Sprache keine kontextfreie Sprache ist, da sie Eigenschaften beschreibt, die für alle kontextfreien Sprachen gelten müssen. Es liefert somit nur eine notwendige (keine hinreichende) Bedingung für die Klassifikation als kontextfreie Sprache. Ogdens Lemma ist also nicht geeignet um Kontextfreiheit zu beweisen. Das Pumping-Lemma ist ein Spezialfall von Ogdens Lemma. (de) In the theory of formal languages, Ogden's lemma (named after ) is a generalization of the pumping lemma for context-free languages. (en) En informatique théorique, le lemme d'Ogden est un résultat de théorie des langages analogue au lemme de l'étoile. On l'utilise principalement pour démontrer que certains langages ne sont pas algébriques. Il est nommé ainsi d'après William F. Ogden, un informaticien théoricien américain qui l’a publié en 1968. Le lemme d'Ogden est une version plus élaborée du lemme d'itération pour les langages algébriques, aussi connu sous le nom de lemme de Bar-Hillel, Perles et Shamir. Il existe des langages qui satisfont le lemme d'Ogden mais qui ne sont pas algébriques. Ce lemme donne une condition nécessaire pour les langages algébriques, mais pas une condition suffisante. Il est très utile, dans sa version grammaticale, pour prouver que certains langages sont inhéremment ambigus. (fr) Nella teoria dei linguaggi formali, il lemma di Ogden è una generalizzazione del pumping lemma per i linguaggi liberi dal contesto. Il lemma di Ogden afferma che se L è un linguaggio libero dal contesto, allora esiste un intero p > 0 tale che per ogni stringa z di lunghezza almeno p in L e ogni modo di "marcare" p o più posizioni all'interno di z, si può scrivere z come z = uvwxy dove le stringhe u, v, w, x, e y soddisfano le seguenti condizioni: 1. * vx contiene almeno una posizione marcata; 2. * vwx ha al massimo p posizioni marcate 3. * uviwxiy appartiene ad L per ogni i > 0. Nel caso particolare in cui tutte le posizioni di z sono marcate, questo risultato si riduce al pumping lemma per i linguaggi liberi dal contesto. Il lemma di Ogden permette di dimostrare la non-appartenenza di certi linguaggi alla classe dei linguaggi liberi dal contesto, anche in alcuni casi in cui il pumping lemma non è sufficiente. Un esempio è il linguaggio {aibjckdl : i = 0 oppure j = k = l}. È utile anche per dimostrare l' di alcuni linguaggi. (it) オグデンの補題（英: Ogden's lemma）とは、形式言語の理論において、文脈自由言語の反復補題の柔軟性を拡張したものである。 具体的には次の通りである。言語 L が文脈自由であるとき、ある正の数 p が存在し（p は反復長とは限らない）、L における p 以上の長さの任意の文字列 w について、w 上の p 個以上の位置（文字）をマークする全ての組合せを考える。w は次のように表される。 w = uvxyz ここで、u, v, x, y, z という文字列について、vy が少なくとも1つのマークされた位置を含み（すなわち |vy |
| dbo:wikiPageExternalLink | https://archive.org/details/introductiontoau00hopc |
| dbo:wikiPageID | 4105321 (xsd:integer) |
| dbo:wikiPageLength | 3579 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 976735003 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Lemmas dbr:Pumping_lemma_for_context-free_languages dbr:Ambiguous_grammar dbr:Formal_language dbc:Formal_languages dbr:William_F._Ogden |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Cite_book dbt:Cite_journal dbt:Mvar dbt:Reflist |
| dct:subject | dbc:Lemmas dbc:Formal_languages |
| 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 | Ogdens Lemma, benannt nach , ist eine Methode der theoretischen Informatik, mit der gezeigt werden kann, dass eine formale Sprache keine kontextfreie Sprache ist, da sie Eigenschaften beschreibt, die für alle kontextfreien Sprachen gelten müssen. Es liefert somit nur eine notwendige (keine hinreichende) Bedingung für die Klassifikation als kontextfreie Sprache. Ogdens Lemma ist also nicht geeignet um Kontextfreiheit zu beweisen. Das Pumping-Lemma ist ein Spezialfall von Ogdens Lemma. (de) In the theory of formal languages, Ogden's lemma (named after ) is a generalization of the pumping lemma for context-free languages. (en) オグデンの補題（英: Ogden's lemma）とは、形式言語の理論において、文脈自由言語の反復補題の柔軟性を拡張したものである。 具体的には次の通りである。言語 L が文脈自由であるとき、ある正の数 p が存在し（p は反復長とは限らない）、L における p 以上の長さの任意の文字列 w について、w 上の p 個以上の位置（文字）をマークする全ての組合せを考える。w は次のように表される。 w = uvxyz ここで、u, v, x, y, z という文字列について、vy が少なくとも1つのマークされた位置を含み（すなわち |vy |
| rdfs:label | Ogdens Lemma (de) Lemme d'Ogden (fr) Lemma di Ogden (it) オグデンの補題 (ja) Ogden's lemma (en) Lemat Ogdena (pl) Lema de Ogden (pt) Лемма Огдена (ru) 鄂登引理 (zh) |
| owl:sameAs | freebase:Ogden's lemma yago-res:Ogden's lemma wikidata:Ogden's lemma dbpedia-de:Ogden's lemma dbpedia-fa:Ogden's lemma dbpedia-fr:Ogden's lemma dbpedia-hr:Ogden's lemma dbpedia-it:Ogden's lemma dbpedia-ja:Ogden's lemma dbpedia-pl:Ogden's lemma dbpedia-pt:Ogden's lemma dbpedia-ru:Ogden's lemma dbpedia-zh:Ogden's lemma https://global.dbpedia.org/id/o562 |
| prov:wasDerivedFrom | wikipedia-en:Ogden's_lemma?oldid=976735003&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Ogden's_lemma |
| is dbo:wikiPageDisambiguates of | dbr:Ogden |
| is dbo:wikiPageRedirects of | dbr:Ogden_lemma |
| is dbo:wikiPageWikiLink of | dbr:List_of_lemmas dbr:Ogden dbr:Pumping_lemma_for_regular_languages dbr:Context-free_language dbr:Pumping_lemma_for_context-free_languages dbr:Pumping_lemma dbr:Ogden_lemma |
| is foaf:primaryTopic of | wikipedia-en:Ogden's_lemma |