Context-sensitive grammar (original) (raw)
Die kontextsensitiven Grammatiken (kurz CSG, von engl. context-sensitive grammar) sind eine Klasse formaler Grammatiken und identisch mit den Typ-1-Grammatiken der Chomsky-Hierarchie. Sie zeichnen sich dadurch aus, dass einzelne Nichtterminalsymbole nur in einem vorgegebenen Kontext ersetzt werden dürfen.
| Property | Value | |
|---|---|---|
| dbo:abstract | En lingüística i informàtica, una gramàtica sensible al context és una gramàtica formal en la qual cada regla dreta o esquerra de producció es pot embolcallar per un context de símbols terminals i no terminals. Les gramàtiques sensibles al context son més generals que les gramàtiques lliures de context, en el sentit que hi ha llenguatges que es poden descriure amb una gramàtica sensible al context però no amb una gramàtica lliure de context. Un llenguatge formal que es pot descriure amb una gramàtica sensible al context s'anomena un llenguatge sensible al context. Les gramàtiques sensibles al context estan classificades com de tipus 1 a la jerarquia de Chomsky. Aquestes gramàtiques van ser introduïdes per Chomsky com un intent de descriure la sintaxi del llenguatge natural donat que una paraula pot ser adequada en una certa posició depenent del context. (ca) Kontextová gramatika je formální gramatika G = (N, Σ, P, S), ve které jsou pravidla v P tvaru αAβ → αγβ kde A ∈ N (to znamená, že A je jeden neterminál) a α, β ∈ (N ∪ Σ)* (to znamená, že α a β jsou řetězce neterminálů a terminálů) a γ ∈ (N ∪ Σ)+ (to znamená, že γ je neprázdný řetězec terminálů a neterminálů). Pokud se S nevyskytuje na pravé straně žádného pravidla, může gramatika obsahovat i pravidlo S → ε kde ε značí prázdný řetězec. Název kontextová je odvozen od faktu, že α a β tvoří kontext, který určuje, zda A lze přepsat na γ. Speciálním případem kontextové gramatiky je gramatika, u které kontext nehraje roli (α i β jsou ve všech pravidlech prázdné). Taková gramatika se označuje jako bezkontextová, bezkontextové gramatiky jsou tedy podmnožinou kontextových gramatik. Formální jazyk popsaný kontextovou gramatikou se nazývá kontextový jazyk. S myšlenkou kontextových gramatik přišel Noam Chomsky ve snaze popsat syntax přirozeného jazyka, ve kterém lze určité slovo použít právě v závislosti na okolním kontextu. (cs) Die kontextsensitiven Grammatiken (kurz CSG, von engl. context-sensitive grammar) sind eine Klasse formaler Grammatiken und identisch mit den Typ-1-Grammatiken der Chomsky-Hierarchie. Sie zeichnen sich dadurch aus, dass einzelne Nichtterminalsymbole nur in einem vorgegebenen Kontext ersetzt werden dürfen. (de) A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are languages that can be described by CSG but not by context-free grammars. Context-sensitive grammars are less general (in the same sense) than unrestricted grammars. Thus, CSG are positioned between context-free and unrestricted grammars in the Chomsky hierarchy. A formal language that can be described by a context-sensitive grammar, or, equivalently, by a noncontracting grammar or a linear bounded automaton, is called a context-sensitive language. Some textbooks actually define CSGs as non-contracting, although this is not how Noam Chomsky defined them in 1959. This choice of definition makes no difference in terms of the languages generated (i.e. the two definitions are weakly equivalent), but it does make a difference in terms of what grammars are structurally considered context-sensitive; the latter issue was analyzed by Chomsky in 1963. Chomsky introduced context-sensitive grammars as a way to describe the syntax of natural language where it is often the case that a word may or may not be appropriate in a certain place depending on the context. Walter Savitch has criticized the terminology "context-sensitive" as misleading and proposed "non-erasing" as better explaining the distinction between a CSG and an unrestricted grammar. Although it is well known that certain features of languages (e.g. cross-serial dependency) are not context-free, it is an open question how much of CSG's expressive power is needed to capture the context sensitivity found in natural languages. Subsequent research in this area has focused on the more computationally tractable mildly context-sensitive languages. The syntaxes of some visual programming languages can be described by context-sensitive graph grammars. (en) Una gramática sensible al contexto es una gramática formal que se define como una cuádrupla G = (N, Σ, P, S) en donde: * N es un alfabeto de símbolo no terminales (variables) * Σ es un alfabeto de símbolos terminales con N ∩ Σ = ∅ * S ∈ N es el símbolo inicial * P es el conjunto finito de producciones de la forma α → β, donde α y β ∈ (N ∪ Σ)+ y |α | ≤ |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20110708224600/https:/danielmattosroberts.com/earley/context-sensitive-earley.pdf | |
| dbo:wikiPageID | 6211 (xsd:integer) | |
| dbo:wikiPageLength | 26874 (xsd:nonNegativeInteger) | |
| dbo:wikiPageRevisionID | 1124873099 (xsd:integer) | |
| dbo:wikiPageWikiLink | dbr:John_Myhill dbr:Decision_problem dbr:Definite_clause_grammar dbr:Kuroda_normal_form dbr:PSPACE-complete dbr:Complement_(set_theory) dbr:Concatenation dbr:Context-free_grammar dbr:S.-Y._Kuroda dbr:Empty_string dbr:Generalized_context-free_grammar dbr:Context-free_language dbr:Context-sensitive_language dbr:Reflexive_transitive_closure dbr:Combinatory_categorial_grammar dbr:Computational_linguistics dbr:Emptiness_problem dbr:Start_symbol_(formal_languages) dbr:String_substitution dbr:Tree-adjoining_grammar dbr:Walter_Savitch dbr:Cross-serial_dependency dbr:Linear_bounded_automaton dbr:Unrestricted_grammar dbr:Recursively_enumerable_language dbr:Noam_Chomsky dbr:Nonterminal_symbol dbr:Formal_grammar dbr:Formal_language dbr:Production_(computer_science) dbr:Recursively_enumerable dbr:Intersection_(set_theory) dbr:Terminal_symbol dbc:Formal_languages dbc:Grammar_frameworks dbr:Chomsky_hierarchy dbr:Growing_context-sensitive_grammar dbr:Graph_grammar dbr:Kleene_plus dbr:Union_(set_theory) dbr:Visual_programming_language dbr:Immerman–Szelepcsényi_theorem dbr:Natural_language dbr:Linear_context-free_rewriting_system dbr:Noncontracting_grammar dbr:Inverse_string_homomorphism dbr:Range_concatenation_grammar dbr:Weak_equivalence_(formal_languages) dbr:List_of_parser_generators_for_context-sensitive_grammars dbr:P=NP_problem dbr:PTIME dbr:Mildly_context-sensitive_language dbr:Revesz'_trick dbr:Penttonen_normal_form dbr:Unbounded_scrambling dbr:Undecidable_language dbr:String_homomorphism dbr:Coupled_context-free_language | |
| dbp:wikiPageUsesTemplate | dbt:As_of dbt:Citation_needed dbt:Cite_book dbt:Cn dbt:More_citations_needed_section dbt:Not_a_typo dbt:Reflist dbt:See_also dbt:Short_description dbt:Formal_languages_and_grammars | |
| dcterms:subject | dbc:Formal_languages dbc:Grammar_frameworks | |
| gold:hypernym | dbr:Grammar | |
| rdf:type | owl:Thing yago:Abstraction100002137 yago:Cognition100023271 yago:Communication100033020 yago:Concept105835747 yago:Content105809192 yago:Hypothesis105888929 yago:Idea105833840 yago:Language106282651 yago:Model105890249 yago:PsychologicalFeature100023100 yago:WikicatGrammarFrameworks dbo:Book yago:WikicatFormalLanguages | |
| rdfs:comment | Die kontextsensitiven Grammatiken (kurz CSG, von engl. context-sensitive grammar) sind eine Klasse formaler Grammatiken und identisch mit den Typ-1-Grammatiken der Chomsky-Hierarchie. Sie zeichnen sich dadurch aus, dass einzelne Nichtterminalsymbole nur in einem vorgegebenen Kontext ersetzt werden dürfen. (de) 文脈依存文法（ぶんみゃくいぞんぶんぽう、英: context-sensitive grammar）は、形式文法 G = (N, Σ, P, S) において P の生成規則が以下のような形式のものをいう。 αAβ → αγβ ここで A は N に属する非終端記号であり、α と β は (N ∪ Σ)* である（すなわち α と β は非終端記号と終端文字から構成される文字列である）。また、γ は (N ∪ Σ)+ である（すなわち γ は空でない非終端記号と終端文字で構成される文字列である）。さらに、以下のような生成規則が存在することもある。 S → ε ここで、ε は空の文字列である。ただしこのとき、S が生成規則の右側に出現してはならない。この規則を許すことで、空文字列を含む文脈依存言語の定義が可能になり、文脈依存言語が文脈自由言語を真に含むと言えるようになる。 (ja) 문맥 의존 문법(文脈依存文法, Context-sensitive grammar, CSG), 문맥 민감 문법은 형식 문법의 한 종류로, 생성규칙에서 시작 부분과 끝부분을 나타내는 것을 포함하는 부분이다. (ko) Een contextgevoelige grammatica, soms ook contextsensitieve grammatica genoemd, is een formele grammatica waarin voor alle productieregels geldt dat de lengte van het linker deel kleiner of gelijk is aan de lengte van het rechter deel. Deze voorwaarde zorgt ervoor dat het beslisbaar is of een gegeven woord door een contextgevoelige grammatica kan worden gegenereerd. (nl) Контекстно зависимая грамматика (КЗ-грамматика, контекстная грамматика) — частный случай формальной грамматики (тип 1 по иерархии Хомского), у которой левые и правые части всех продукций могут быть окружены терминальными и нетерминальными символами. Частным случаем формальной грамматики также является контекстно-свободная грамматика. Язык, который может быть задан КЗ-грамматикой, называется контекстно зависимым языком или КЗ-языком. (ru) Контекстно-залежна граматика (скорочено КЗ-граматика) — формальна граматика типу 1 в ієрархії Чомскі. Особливість КЗ граматик в тому, що правила виводу здійснюють заміну символу лише у визначеному контексті. (uk) 上下文有关文法(CSG，英語：context-sensitive grammar)是一種形式文法，其中任何规则的左手端和右手端都可以被终结符和非终结符構成的上下文所围绕。上下文有关文法比上下文无关文法更一般性，但仍足够有秩序得可以被线性有界自动机所解析。 上下文有关文法的概念是诺姆·乔姆斯基在1950年代介入的，被作为描述自然语言的语法的一种方式，在自然语言中一个单词是否可以出现在特定位置上，要依赖于上下文。可以被上下文有关文法描述的形式语言叫做上下文有关语言。 (zh) En lingüística i informàtica, una gramàtica sensible al context és una gramàtica formal en la qual cada regla dreta o esquerra de producció es pot embolcallar per un context de símbols terminals i no terminals. Les gramàtiques sensibles al context son més generals que les gramàtiques lliures de context, en el sentit que hi ha llenguatges que es poden descriure amb una gramàtica sensible al context però no amb una gramàtica lliure de context. Un llenguatge formal que es pot descriure amb una gramàtica sensible al context s'anomena un llenguatge sensible al context. (ca) Kontextová gramatika je formální gramatika G = (N, Σ, P, S), ve které jsou pravidla v P tvaru αAβ → αγβ kde A ∈ N (to znamená, že A je jeden neterminál) a α, β ∈ (N ∪ Σ)* (to znamená, že α a β jsou řetězce neterminálů a terminálů) a γ ∈ (N ∪ Σ)+ (to znamená, že γ je neprázdný řetězec terminálů a neterminálů). Pokud se S nevyskytuje na pravé straně žádného pravidla, může gramatika obsahovat i pravidlo S → ε kde ε značí prázdný řetězec. (cs) A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are languages that can be described by CSG but not by context-free grammars. Context-sensitive grammars are less general (in the same sense) than unrestricted grammars. Thus, CSG are positioned between context-free and unrestricted grammars in the Chomsky hierarchy. (en) Una gramática sensible al contexto es una gramática formal que se define como una cuádrupla G = (N, Σ, P, S) en donde: * N es un alfabeto de símbolo no terminales (variables) * Σ es un alfabeto de símbolos terminales con N ∩ Σ = ∅ * S ∈ N es el símbolo inicial * P es el conjunto finito de producciones de la forma α → β, donde α y β ∈ (N ∪ Σ)+ y |α | ≤ |
| rdfs:label | Gramàtica sensible al context (ca) Kontextová gramatika (cs) Kontextsensitive Grammatik (de) Gramáticas sensibles al contexto (es) Context-sensitive grammar (en) Grammatica dipendente dal contesto (it) Grammaire contextuelle (fr) 문맥 의존 문법 (ko) 文脈依存文法 (ja) Contextgevoelige grammatica (nl) Gramatyka kontekstowa (pl) Gramática sensível ao contexto (pt) Контекстно-зависимая грамматика (ru) 上下文有关文法 (zh) Контекстно-залежна граматика (uk) | |
| rdfs:seeAlso | dbr:Context-sensitive_language | |
| owl:sameAs | freebase:Context-sensitive grammar yago-res:Context-sensitive grammar wikidata:Context-sensitive grammar dbpedia-ca:Context-sensitive grammar dbpedia-cs:Context-sensitive grammar dbpedia-de:Context-sensitive grammar dbpedia-es:Context-sensitive grammar dbpedia-fa:Context-sensitive grammar dbpedia-fr:Context-sensitive grammar dbpedia-he:Context-sensitive grammar dbpedia-hr:Context-sensitive grammar dbpedia-it:Context-sensitive grammar dbpedia-ja:Context-sensitive grammar dbpedia-ko:Context-sensitive grammar dbpedia-nl:Context-sensitive grammar dbpedia-pl:Context-sensitive grammar dbpedia-pt:Context-sensitive grammar dbpedia-ru:Context-sensitive grammar dbpedia-sh:Context-sensitive grammar dbpedia-sk:Context-sensitive grammar dbpedia-sr:Context-sensitive grammar dbpedia-uk:Context-sensitive grammar dbpedia-zh:Context-sensitive grammar https://global.dbpedia.org/id/54Mpt | |
| prov:wasDerivedFrom | wikipedia-en:Context-sensitive_grammar?oldid=1124873099&ns=0 | |
| foaf:isPrimaryTopicOf | wikipedia-en:Context-sensitive_grammar | |
| is dbo:wikiPageDisambiguates of | dbr:Context-sensitive dbr:CSG | |
| is dbo:wikiPageRedirects of | dbr:Context-dependent_grammar dbr:Context_sensitive_grammar | |
| is dbo:wikiPageWikiLink of | dbr:Pāṇini dbr:List_of_computability_and_complexity_topics dbr:List_of_formal_language_and_literal_string_topics dbr:Definite_clause_grammar dbr:Index_of_computing_articles dbr:Index_of_philosophy_articles_(A–C) dbr:Index_of_philosophy_of_language_articles dbr:Kuroda_normal_form dbr:Lexer_hack dbr:PSPACE-complete dbr:Context-free_grammar dbr:MediaWiki dbr:S.-Y._Kuroda dbr:NooJ dbr:Bounded_quantifier dbr:Context-sensitive_language dbr:Context_model dbr:Mildly_context-sensitive_grammar_formalism dbr:Comparison_of_parser_generators dbr:Complexity_class dbr:Computational_linguistics dbr:Embedded_pushdown_automaton dbr:Emptiness_problem dbr:Speech_synthesis dbr:Syntax_(programming_languages) dbr:Theory_of_computation dbr:Tree-adjoining_grammar dbr:Matrix_grammar dbr:Phrase_structure_grammar dbr:Adaptive_grammar dbr:Ambiguous_grammar dbr:Chomsky_hierarchy dbr:Context-sensitive dbr:Greibach's_theorem dbr:Growing_context-sensitive_grammar dbr:Sheila_Greibach dbr:CSG dbr:Van_Wijngaarden_grammar dbr:Extended_affix_grammar dbr:KNF dbr:Structure_editor dbr:Noncontracting_grammar dbr:Raku_rules dbr:Context-dependent_grammar dbr:Context_sensitive_grammar | |
| is foaf:primaryTopic of | wikipedia-en:Context-sensitive_grammar |