Context-free language (original) (raw)
Bezkontextový jazyk je formální jazyk, který je akceptovaný nějakým zásobníkovým automatem. Bezkontextové jazyky mohou být vygenerovány bezkontextovými gramatikami (viz Chomského hierarchie).
| Property | Value | |||||
|---|---|---|---|---|---|---|
| dbo:abstract | En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge lliure de context si es pot generar amb una gramàtica lliure de context. El conjunt de tots els llenguatges lliures de context és idèntic al conjunt de llenguatges acceptats per un autòmat amb pila, cosa que fa aquests llenguatges adequats per analitzar sintàcticament (parser). A més, donada una gramàtica lliure de context, hi ha una forma directa de generar un autòmat amb pila per dita gramàtica i el seu corresponent llenguatge. L'operació contraria no és directe. Diferents gramàtiques lliures de context poden generar el mateix llenguatge lliure de context. (ca) Bezkontextový jazyk je formální jazyk, který je akceptovaný nějakým zásobníkovým automatem. Bezkontextové jazyky mohou být vygenerovány bezkontextovými gramatikami (viz Chomského hierarchie). (cs) 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. (de) In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by context-free grammars. (en) 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 un 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. Plusieurs équivalents sont employés et équivalents : langage « context-free » ou langage non contextuel, langage hors-contexte[réf. souhaitée], langage acontextuel. (fr) 문맥 자유 언어(文脈自由言語, Context-free language, CFL)는 문맥 자유 문법이 생성하는 형식 언어이다. 문맥 자유 언어는 프로그래밍 언어의 연구에서 중요한 역할을 한다. (ko) 文脈自由言語（ぶんみゃくじゆうげんご）とは、次のような再帰的な生成規則をもつ文脈自由文法によって、与えられた言語の長さ n に対して O(n3) の時間で認識される形式言語。プッシュダウン・オートマトンで受理可能な言語と等価である。 * S → E. * E → T | E - T | E + T | (E). * T → T * E | T / E | id | num. ある言語が文脈自由言語でないことを証明するために文脈自由言語の反復補題が使われることがある。 (ja) 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) 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 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) 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. W hierarchii Chomsky’ego jest zdefiniowany jako język typu 2. 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) 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 | http://www-igm.univ-mlv.fr/~berstel/Articles/1997CFLPDA.pdf https://archive.org/details/introductiontoth00sips https://archive.org/details/introductiontoau00hopc | |||||
| dbo:wikiPageID | 6867 (xsd:integer) | |||||
| dbo:wikiPageLength | 14531 (xsd:nonNegativeInteger) | |||||
| dbo:wikiPageRevisionID | 1122395910 (xsd:integer) | |||||
| dbo:wikiPageWikiLink | dbr:Prefix_(computer_science) dbr:Programming_languages dbr:Pushdown_automaton dbr:Parsing dbr:Deterministic_context-free_language dbr:Deterministic_pushdown_automaton dbr:Lillian_Lee_(computer_scientist) dbr:Concatenation dbr:Context-free_grammar dbr:Matrix_multiplication dbr:Ogden's_lemma dbr:Parikh's_theorem dbr:Quotient_of_a_formal_language dbr:Context-sensitive_language dbr:LR_parser dbr:Leslie_Valiant dbr:Closure_(mathematics) dbr:Parsing_expression_grammar dbr:String_operations dbc:Syntax dbr:Pumping_lemma_for_context-free_languages dbr:Dyck_language dbr:Earley_parser dbr:Formal_language_theory dbr:Formal_language dbr:Regular_language dbc:Formal_languages dbr:Chomsky_normal_form dbr:Big_O_notation dbr:CYK_algorithm dbr:Circular_shift dbr:Pushdown_automata dbr:Yehoshua_Bar-Hillel dbr:Kleene_star dbr:Undecidable_problem dbr:Union_(set_theory) dbr:Inherently_ambiguous_language dbr:Membership_problem | |||||
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Cite_book dbt:Main dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfn dbt:Formal_languages_and_grammars | |||||
| dcterms:subject | dbc:Syntax dbc:Formal_languages | |||||
| rdf:type | yago:WikicatLanguages yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 yago:WikicatFormalLanguages | |||||
| rdfs:comment | Bezkontextový jazyk je formální jazyk, který je akceptovaný nějakým zásobníkovým automatem. Bezkontextové jazyky mohou být vygenerovány bezkontextovými gramatikami (viz Chomského hierarchie). (cs) In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by context-free grammars. (en) 문맥 자유 언어(文脈自由言語, Context-free language, CFL)는 문맥 자유 문법이 생성하는 형식 언어이다. 문맥 자유 언어는 프로그래밍 언어의 연구에서 중요한 역할을 한다. (ko) 文脈自由言語（ぶんみゃくじゆうげんご）とは、次のような再帰的な生成規則をもつ文脈自由文法によって、与えられた言語の長さ 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. W hierarchii Chomsky’ego jest zdefiniowany jako język typu 2. 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) En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge lliure de context si es pot generar amb una gramàtica lliure de context. El conjunt de tots els llenguatges lliures de context és idèntic al conjunt de llenguatges acceptats per un autòmat amb pila, cosa que fa aquests llenguatges adequats per analitzar sintàcticament (parser). A més, donada una gramàtica lliure de context, hi ha una forma directa de generar un autòmat amb pila per dita gramàtica i el seu corresponent llenguatge. L'operació contraria no és directe. (ca) 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) 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 un 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) 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) 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 | Llenguatge lliure de context (ca) Bezkontextový jazyk (cs) Kontextfreie Sprache (de) Context-free language (en) Linguaggio libero dal contesto (it) Langage algébrique (fr) 문맥 자유 언어 (ko) 文脈自由言語 (ja) Contextvrije taal (nl) Język bezkontekstowy (pl) Linguagem livre de contexto (pt) 上下文无关语言 (zh) | |||||
| owl:sameAs | freebase:Context-free language yago-res:Context-free language wikidata:Context-free language http://bs.dbpedia.org/resource/Kontekstno_nezavisni_jezik dbpedia-ca:Context-free language dbpedia-cs:Context-free language dbpedia-de:Context-free language dbpedia-fa:Context-free language dbpedia-fi:Context-free language dbpedia-fr:Context-free language dbpedia-he:Context-free language dbpedia-hr:Context-free language dbpedia-it:Context-free language dbpedia-ja:Context-free language dbpedia-ko:Context-free language dbpedia-nl:Context-free language dbpedia-nn:Context-free language dbpedia-no:Context-free language dbpedia-pl:Context-free language dbpedia-pt:Context-free language dbpedia-ro:Context-free language dbpedia-sh:Context-free language dbpedia-sr:Context-free language dbpedia-zh:Context-free language https://global.dbpedia.org/id/4tsk4 | |||||
| prov:wasDerivedFrom | wikipedia-en:Context-free_language?oldid=1122395910&ns=0 | |||||
| foaf:isPrimaryTopicOf | wikipedia-en:Context-free_language | |||||
| is dbo:wikiPageDisambiguates of | dbr:Context-free dbr:CFL_(disambiguation) | |||||
| is dbo:wikiPageRedirects of | dbr:Context-Free_Language dbr:Non-context-free_language dbr:Context-Free_languages dbr:Context-free_languages dbr:Context_Free_Languages dbr:Context_free_language | |||||
| is dbo:wikiPageWikiLink of | dbr:Pushdown_automaton dbr:Scannerless_parsing dbr:List_of_complexity_classes dbr:Parsing dbr:David_E._Muller dbr:Deep_structure_and_surface_structure dbr:History_of_compiler_construction dbr:Paul_Schupp dbr:Regular_expression dbr:Cyclic_language dbr:Deterministic_context-free_language dbr:Deterministic_pushdown_automaton dbr:Index_of_philosophy_articles_(A–C) dbr:Indexed_language dbr:JFLAP dbr:Computability dbr:Context-free_grammar dbr:Chomsky–Schützenberger_theorem dbr:Parikh's_theorem dbr:GNU_Bison dbr:Cone_(formal_languages) dbr:Conjunctive_grammar dbr:Context-sensitive_grammar dbr:Context-sensitive_language dbr:Cross-serial_dependencies dbr:Equivalence_problem dbr:LL_parser dbr:LOGCFL dbr:Chomsky–Schützenberger_enumeration_theorem dbr:Chomsky–Schützenberger_representation_theorem dbr:Combinatorics_on_words dbr:Comparison_of_parser_generators dbr:Computation_history dbr:Helmut_Alt dbr:Micha_Perles dbr:Parsing_expression_grammar dbr:Pattern_language_(formal_languages) dbr:Syntax_(programming_languages) dbr:String_operations dbr:Language_identification_in_the_limit dbr:Laws_of_Form dbr:Linear_grammar dbr:Mireille_Bousquet-Mélou dbr:Pumping_lemma_for_context-free_languages dbr:Recursively_enumerable_language dbr:Dyck_language dbr:Earley_parser dbr:Alternation_(formal_language_theory) dbr:Ambiguous_grammar dbr:Discontinuous-constituent_phrase_structure_grammar dbr:Formal_grammar dbr:Formal_language dbr:Syntactic_predicate dbr:Abstract_family_of_languages dbr:Chomsky_hierarchy dbr:John_Backus dbr:Swiss_German dbr:Edit_distance dbr:Top-down_parsing_language dbr:Read-only_Turing_machine dbr:Recursive_grammar dbr:Recursive_language dbr:Automata_theory dbr:Circular_shift dbr:Context-Free_Language dbr:Context-free dbr:Greibach's_theorem dbr:Greibach_normal_form dbr:Kleene_algebra dbr:Metasyntax dbr:Brzozowski_derivative dbr:Natural-language_programming dbr:Seymour_Ginsburg dbr:CFL_(disambiguation) dbr:SC_(complexity) dbr:Runtime_verification dbr:Non-context-free_language dbr:The_Art_of_Computer_Programming dbr:Noncontracting_grammar dbr:Muller–Schupp_theorem dbr:Palindrome dbr:Outline_of_natural_language_processing dbr:Context-Free_languages dbr:Context-free_languages dbr:Context_Free_Languages dbr:Context_free_language | |||||
| is foaf:primaryTopic of | wikipedia-en:Context-free_language |