In formal language theory, a context-free language (CFL) is a language generated by some context-free grammar (CFG). Different CF grammars can generate the same CF language. It is important to distinguish properties of the language (intrinsic properties) from properties of a particular grammar (extrinsic properties). Context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar . Also, most arithmetic expressions are generated by context-free grammars.

Property Value
dbo:abstract
  • In formal language theory, a context-free language (CFL) is a language generated by some context-free grammar (CFG). Different CF grammars can generate the same CF language. It is important to distinguish properties of the language (intrinsic properties) from properties of a particular grammar (extrinsic properties). The set of all context-free languages is identical to the set of languages accepted by pushdown automata, which makes these languages amenable to parsing. Indeed, given a CFG, there is a direct way to produce a pushdown automaton for the grammar (and corresponding language), though going the other way (producing a grammar given an automaton) is not as direct. Context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar . Also, most arithmetic expressions are generated by context-free grammars. (en)
  • In der Theoretischen Informatik ist eine kontextfreie Sprache (englisch context-free language, CFL) eine formale Sprache, die durch eine kontextfreie Grammatik beschrieben werden kann. Eine kontextfreie Grammatik erlaubt einen definierten Leseprozess (Interpretation) von Ausdrücken einer formalen Sprache. Dabei kann zum einen entschieden werden, ob ein Ausdruck den Regeln der Grammatik entspricht, und zum anderen im Verlauf der Analyse ein Syntaxbaum erstellt werden. Ein Programm, das dies leistet, heißt Parser. Parser werden insbesondere zur Verarbeitung von Programmiersprachen verwendet. Auch in der Computerlinguistik versucht man, natürliche Sprachen durch Regeln kontextfreier Grammatiken zu beschreiben. Kontextfreie Sprachen werden auch als Typ-2-Sprachen der Chomsky-Hierarchie bezeichnet. Die Klasse aller kontextfreien Sprachen beinhaltet die regulären Sprachen (Typ-3-Sprachen) und wird von der Klasse der kontextsensitiven Sprachen (Typ-1-Sprachen) umfasst. Man spricht deshalb von kontextfreien Sprachen, weil die Regeln der kontextfreien Grammatiken immer vom Kontext unabhängig angewendet werden. Das unterscheidet sie von kontextsensitiven Grammatiken, deren Regeln auch vom syntaktischen Kontext abhängen. (de)
  • En théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui est engendré par une grammaire algébrique. De manière équivalente un langage algébrique est un langage reconnu par automate à pile. Les langages algébriques forment les langages de type 2 dans la hiérarchie de Chomsky. Ils ont des applications importantes dans la description des langages de programmation et en linguistique. Ils interviennent également dans la description des langages XML. On trouve plusieurs termes pour désigner un langage algébrique; ceci provient du fait que le terme anglais « context-free » est malcommode à traduire. On peut se contenter de le mettre entre guillemets : langage « context-free », ou le traduire par langage non contextuel, langage hors-contexte, langage acontextuel; tous ces termes sont employés et équivalents. (fr)
  • Un linguaggio libero dal contesto (o non contestuale, o context-free) è un linguaggio formale generato da una grammatica che sia, appunto, non contestuale, ovvero tale che le cui regole agiscono su simboli non terminali a prescindere dal contesto in cui essi appaiono. L'insieme dei linguaggi liberi da contesto è equivalente all'insieme dei linguaggi che sono riconoscibili da un automa a pila non deterministico.La semplicità del tipo di automa necessario al loro riconoscimento e il fatto che lo stesso possa essere generato direttamente dalla definizione della grammatica, rendono tale classe di linguaggi di particolare interesse nell'informatica teorica ed in particolare nella teoria dei linguaggi di programmazione e della loro implementazione. (it)
  • 文脈自由言語(ぶんみゃくじゆうげんご)とは、次のような再帰的な生成規則をもつ文脈自由文法によって、与えられた言語の長さ n に対して O(n3) の時間で認識される形式言語。プログラミング言語の文法を記述するのに使われる。プッシュダウン・オートマトンで受理可能な言語と等価である。 * S → E. * E → T | E - T | E + T | (E). * T → T * E | T / E | id | num. ある言語が文脈自由言語でないことを証明するために文脈自由言語の反復補題が使われることがある。 (ja)
  • Język bezkontekstowy (ang. context-free language) – język formalny taki, że istnieje niedeterministyczny automat ze stosem decydujący czy dany łańcuch należy do języka. Równoważnie, taki, że istnieje dlań gramatyka bezkontekstowa. Rodzina języków regularnych jest podzbiorem zbioru języków bezkontekstowych.Każdy język bezkontekstowy jest językiem kontekstowym. Języki bezkontekstowe mają ważne znaczenie w informatyce, m.in. w budowie kompilatorów; patrz analiza składniowa. (pl)
  • In de theoretische informatica is een contextvrije taal een formele taal die door een contextvrije grammatica gegenereerd wordt. Een alternatieve karakterisering van een contextvrije taal is een taal die door een stapelautomaat geaccepteerd wordt. In de Chomskyhiërarchie zitten de contextvrije talen tussen de reguliere en contextsensitieve talen in. Elke reguliere taal is ook een contextvrije taal en elke contextvrije taal ook een contextsensitieve. Aan de andere kant bestaan er contextvrije talen die niet regulier zijn en contextsensitieve talen die niet contextvrij zijn. Omdat contextvrije talen aan de ene kant niet zo begrensd zijn als reguliere talen, maar aan de andere kant begrensd genoeg om efficiënt herkend (geparsed) te worden, worden contextvrije talen vaak gebruikt in natuurlijke taalherkenning en in de compilerbouw. (nl)
  • Na teoria de linguagens formais, uma linguagem livre de contexto (LLC) é uma linguagem gerada por alguma gramática livre de contexto (GLC). Diferentes gramáticas livres de contexto podem gerar a mesma linguagem livre de contexto, ou, inversamente, uma dada linguagem livre de contexto pode ser gerada por diferentes gramáticas livres de contexto. É importante distinguir as propriedades da linguagem ( propriedades intrínsecas ) de propriedades de uma gramática específica ( propriedades extrínsecas ). O conjunto de todas as linguagens livres de contexto é idêntico ao conjunto de linguagens aceitas por um autômato de pilha., o que faz com que essas linguagens sejam passíveis de análise. Na verdade, dada uma GLC, há uma maneira direta para produzir um autômato com pilha para a gramática (e linguagem correspondente ), mas indo para o outro lado (produzindo uma gramática dado um autômato ) não é tão direta. (pt)
  • 上下文无关语言是可以用上下文无关文法定义的形式语言。所有上下文无关语言的集合同一于下推自动机所接受的语言的集合。 (zh)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 6867 (xsd:integer)
dbo:wikiPageRevisionID
  • 722587537 (xsd:integer)
dct:subject
rdf:type
rdfs:comment
  • 文脈自由言語(ぶんみゃくじゆうげんご)とは、次のような再帰的な生成規則をもつ文脈自由文法によって、与えられた言語の長さ n に対して O(n3) の時間で認識される形式言語。プログラミング言語の文法を記述するのに使われる。プッシュダウン・オートマトンで受理可能な言語と等価である。 * S → E. * E → T | E - T | E + T | (E). * T → T * E | T / E | id | num. ある言語が文脈自由言語でないことを証明するために文脈自由言語の反復補題が使われることがある。 (ja)
  • Język bezkontekstowy (ang. context-free language) – język formalny taki, że istnieje niedeterministyczny automat ze stosem decydujący czy dany łańcuch należy do języka. Równoważnie, taki, że istnieje dlań gramatyka bezkontekstowa. Rodzina języków regularnych jest podzbiorem zbioru języków bezkontekstowych.Każdy język bezkontekstowy jest językiem kontekstowym. Języki bezkontekstowe mają ważne znaczenie w informatyce, m.in. w budowie kompilatorów; patrz analiza składniowa. (pl)
  • 上下文无关语言是可以用上下文无关文法定义的形式语言。所有上下文无关语言的集合同一于下推自动机所接受的语言的集合。 (zh)
  • In formal language theory, a context-free language (CFL) is a language generated by some context-free grammar (CFG). Different CF grammars can generate the same CF language. It is important to distinguish properties of the language (intrinsic properties) from properties of a particular grammar (extrinsic properties). Context-free languages have many applications in programming languages; for example, the language of all properly matched parentheses is generated by the grammar . Also, most arithmetic expressions are generated by context-free grammars. (en)
  • In der Theoretischen Informatik ist eine kontextfreie Sprache (englisch context-free language, CFL) eine formale Sprache, die durch eine kontextfreie Grammatik beschrieben werden kann. Eine kontextfreie Grammatik erlaubt einen definierten Leseprozess (Interpretation) von Ausdrücken einer formalen Sprache. Dabei kann zum einen entschieden werden, ob ein Ausdruck den Regeln der Grammatik entspricht, und zum anderen im Verlauf der Analyse ein Syntaxbaum erstellt werden. Ein Programm, das dies leistet, heißt Parser. Parser werden insbesondere zur Verarbeitung von Programmiersprachen verwendet. Auch in der Computerlinguistik versucht man, natürliche Sprachen durch Regeln kontextfreier Grammatiken zu beschreiben. (de)
  • Un linguaggio libero dal contesto (o non contestuale, o context-free) è un linguaggio formale generato da una grammatica che sia, appunto, non contestuale, ovvero tale che le cui regole agiscono su simboli non terminali a prescindere dal contesto in cui essi appaiono. (it)
  • En théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui est engendré par une grammaire algébrique. De manière équivalente un langage algébrique est un langage reconnu par automate à pile. Les langages algébriques forment les langages de type 2 dans la hiérarchie de Chomsky. Ils ont des applications importantes dans la description des langages de programmation et en linguistique. Ils interviennent également dans la description des langages XML. (fr)
  • In de theoretische informatica is een contextvrije taal een formele taal die door een contextvrije grammatica gegenereerd wordt. Een alternatieve karakterisering van een contextvrije taal is een taal die door een stapelautomaat geaccepteerd wordt. (nl)
  • Na teoria de linguagens formais, uma linguagem livre de contexto (LLC) é uma linguagem gerada por alguma gramática livre de contexto (GLC). Diferentes gramáticas livres de contexto podem gerar a mesma linguagem livre de contexto, ou, inversamente, uma dada linguagem livre de contexto pode ser gerada por diferentes gramáticas livres de contexto. É importante distinguir as propriedades da linguagem ( propriedades intrínsecas ) de propriedades de uma gramática específica ( propriedades extrínsecas ). (pt)
rdfs:label
  • Context-free language (en)
  • Kontextfreie Sprache (de)
  • Linguaggio libero dal contesto (it)
  • Langage algébrique (fr)
  • 文脈自由言語 (ja)
  • Język bezkontekstowy (pl)
  • Contextvrije taal (nl)
  • Linguagem livre de contexto (pt)
  • 上下文无关语言 (zh)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is foaf:primaryTopic of