| dbpprop:abstract
|
- 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 but still orderly enough to be parsed by a linear bounded automaton. The concept of context-sensitive grammar was introduced by Noam Chomsky in the 1950s as a way to describe the syntax of natural language where it is indeed often the case that a word may or may not be appropriate in a certain place depending upon the context. A formal language that can be described by a context-sensitive grammar is called a context-sensitive language.
- Die kontextsensitiven Grammatiken sind eine Klasse formaler Grammatiken und identisch mit den Typ-1-Grammatiken der Chomsky-Hierarchie.
- 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.
- Una gramática sensible al contexto es una gramática formal G = (N, Σ, P, S) tal que todas las producciones P son de la forma: αAβ → αγβ con A en N y α y β en (N U &Sigma)* y γ en (N U &Sigma), con la posibilidad de la regla lambda S → λ con λ, la cadena vacía. Se lo llama sensible al contexto porque α y β determinan la forma que debe tener una cadena que puede ser reemplazada por alguna de las producciones. Una lenguaje formal que puede ser descripto para una gramática sensible al contexto se llama lenguaje sensible al contexto
- Una grammatica sensibile al contesto, o context-sensitive, o di Tipo 1 nella gerarchia di Chomsky, è definita sulla seguente regola di produzione: <math>\alpha \rightarrow \beta, |\alpha| \le |\beta|</math> cioè, per ogni produzione di β, questa non può essere più piccola di α, cioè o ha la stessa cardinalità o è più grande. Una grammatica sensibile al contesto è quindi una grammatica formale G = (N, Σ, P, S) tale che tutte le regole di produzione in P sono nella forma αAβ → αγβ con A in N (i.e. , A è un simbolo nonterminale) e α e β in (N U &Sigma)* (i.e. , α e β stringhe di simboli non terminali e terminali) e γ in (N U &Sigma) (i.e. , γ una stringa non vuota di terminali e non terminali). Le stringhe <math>\alpha</math> e <math>\beta</math> possono essere vuote, ma la <math>\gamma</math> non deve essere vuota. La regola di produzione <math>S \rightarrow \epsilon</math> è permessa se <math>S</math> non appare nel lato destro delle regole di produzione. Il nome sensibile al contesto è spiegato dall' α e β che formano il contesto di A e determinano se A può essere rimpiazzata o no con γ. In una grammatica libera dal contesto, invece, il contesto di un nonterminale non è preso in cosiderazione. Un linguaggio formale che può essere descritto da una grammatica sensibile al contesto è chiamato linguaggio sensibile al contesto. Il concetto di grammatica sensibile al contesto fu introdotto da Noam Chomsky negli anni 50 come modo per descrivere la sintassi di un linguaggio naturale dove si trova spesso il caso che una parola possa o non possa essere appropriata in una certa posizione a seconda del contesto.
- 文脈依存文法（ぶんみゃくいぞんぶんぽう、Context-sensitive Grammar）は、形式文法 G = (N, Σ, P, S) において P の生成規則が以下のような形式のものをいう。 αAβ → αγβ ここで A は N に属する非終端記号であり、α と β は (N U &Sigma)* である（すなわち α と β は非終端記号と終端文字から構成される文字列である）。また、γ は (N U &Sigma) である（すなわち γ は空でない非終端記号と終端文字で構成される文字列である）。さらに、以下のような生成規則が存在する。 S → ε ここで、ε は空の文字列である。S が生成規則の右側に全く出現しない場合もある。 「文脈依存」という用語は、Aの前後の α と β を意味している。つまり A の前後の文脈によって A を γ に置換できるかどうかを判断しているからである。これは文脈自由文法と異なる点であり、文脈自由文法では終端文字列の文脈（つまり非終端記号の前後の終端文字列）は生成規則上無視される。文脈依存文法で記述される形式言語は文脈依存言語と呼ばれる。 文脈依存文法の概念は1950年代にノーム・チョムスキーによって導入されたもので、文脈によってある単語がその位置に存在することが適当か否かが判断される自然言語の文法を記述する方法として考案されたものである。
- Gramatyką kontekstową (and. context-sensitive grammar) – gramatyka formalna, której reguły są postaci: <math>\alpha A \beta \rightarrow \alpha \gamma \beta</math> gdzie <math>A</math> jest symbolem nieterminalnym, <math>\alpha</math>, <math>\beta</math>; są dowolnymi ciągami symboli terminalnych i nieterminalnych (mogą być puste), natomiast <math>\gamma</math> to dowolny niepusty ciąg symboli terminalnych i nieterminalnych. Każda gramatyka kontekstowa definiuje pewien język kontekstowy. Zauważmy, że właściwa reguła to <math>A \rightarrow \gamma</math>, ciągi <math>\alpha</math> i <math>\beta</math> stanowią kontekst, w którym dopuszczalne jest zastosowanie tej reguły, stąd właśnie pochodzi nazwa tej klasy gramatyk. Funkcjonuje również równoważna (z dokładnością do słowa pustego) definicja gramatyki kontekstowej: gramatyką kontekstową nazywamy gramatykę, której reguły są postaci: <math>\alpha \rightarrow \beta</math> gdzie <math>\alpha</math> i <math>\beta</math> są dowolnymi ciągami symboli terminalnych i nieterminalnych spełniającymi warunek: <math>|\alpha| \leqslant |\beta|</math>, gdzie <math>|\alpha|</math> oznacza liczbę symboli w ciągu <math>\alpha</math>. Takie gramatyki nazywamy też gramatykami monotonicznymi z uwagi na to, że liczba symboli podczas wyprowadzania słowa nigdy nie maleje. Gramatyki kontekstowe zostały wprowadzone przez Noama Chomsky'ego w roku 1950 jako sposób formalnego opisu języków naturalnych, w których często poprawność wystąpienia słowa zależy od kontekstu, w którym jest ono umieszone.
- Em Teoria da computação as Gramáticas sensíveis ao contexto são também conhecidas como Tipo 1 da Hierarquia de Chomsky. Se as regras de substituição forem impostas à restrição de que nenhuma substituição possa reduzir o comprimento da forma sentencial à qual a substituição é aplicada, cria-se uma classe chamada sensíveis ao contexto.
- 上下文有关文法(CSG)是其中任何产生规则的左手端和右手端都可以被终结符和非终结符的上下文所围绕的形式文法。上下文有关文法比上下文无关文法更一般性但仍足够有秩序得可以被线性有界自动机所解析。 上下文有关文法的概念是诺姆·乔姆斯基在1950年代作为描述自然语言的语法的一种方式介入的，在自然语言中一个单词是否可以出现在特定位置上要依赖于上下文。可以被上下文有关文法描述的形式语言叫做上下文有关语言。
|
| rdfs:comment
|
- 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 but still orderly enough to be parsed by a linear bounded automaton.
- Die kontextsensitiven Grammatiken sind eine Klasse formaler Grammatiken und identisch mit den Typ-1-Grammatiken der Chomsky-Hierarchie.
- 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ů).
- Una gramática sensible al contexto es una gramática formal G = (N, Σ, P, S) tal que todas las producciones P son de la forma: αAβ → αγβ con A en N y α y β en (N U &Sigma)* y γ en (N U &Sigma), con la posibilidad de la regla lambda S → λ con λ, la cadena vacía. Se lo llama sensible al contexto porque α y β determinan la forma que debe tener una cadena que puede ser reemplazada por alguna de las producciones.
- Una grammatica sensibile al contesto, o context-sensitive, o di Tipo 1 nella gerarchia di Chomsky, è definita sulla seguente regola di produzione: <math>\alpha \rightarrow \beta, |\alpha| \le |\beta|</math> cioè, per ogni produzione di β, questa non può essere più piccola di α, cioè o ha la stessa cardinalità o è più grande.
- Gramatyką kontekstową (and. context-sensitive grammar) – gramatyka formalna, której reguły są postaci: <math>\alpha A \beta \rightarrow \alpha \gamma \beta</math> gdzie <math>A</math> jest symbolem nieterminalnym, <math>\alpha</math>, <math>\beta</math>; są dowolnymi ciągami symboli terminalnych i nieterminalnych (mogą być puste), natomiast <math>\gamma</math> to dowolny niepusty ciąg symboli terminalnych i nieterminalnych.
- Em Teoria da computação as Gramáticas sensíveis ao contexto são também conhecidas como Tipo 1 da Hierarquia de Chomsky. Se as regras de substituição forem impostas à restrição de que nenhuma substituição possa reduzir o comprimento da forma sentencial à qual a substituição é aplicada, cria-se uma classe chamada sensíveis ao contexto.
|
![[RDF Data]](/statics/sw-cube.png)
