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 a CSG but not by a context-free grammar. Context-sensitive grammars are less general (in the same sense) than unrestricted grammars. Thus, CSGs are positioned between context-free and unrestricted grammars in the Chomsky hierarchy.^[1]

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,^[2][3][4][5] although this is not how Noam Chomsky defined them in 1959.^[6][7] 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.^[8][9]

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.^[10]

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 CSGs' 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.^{[citation needed]} The syntaxes of some visual programming languages can be described by context-sensitive graph grammars.^[11]

Formal definition

Formal grammar

Let us notate a formal grammar as ${\displaystyle G=(N,\Sigma ,P,S)}$, with ${\displaystyle N}$ a set of nonterminal symbols, ${\displaystyle \Sigma }$ a set of terminal symbols, ${\displaystyle P}$ a set of production rules, and ${\displaystyle S\in N}$ the start symbol.

A string ${\displaystyle u\in (N\cup \Sigma )^{*}}$ directly yields, or directly derives to, a string ${\displaystyle v\in (N\cup \Sigma )^{*}}$, denoted as ${\displaystyle u\Rightarrow v}$, if v can be obtained from u by an application of some production rule in P, that is, if ${\displaystyle u=\gamma L\delta }$ and ${\displaystyle v=\gamma R\delta }$, where ${\displaystyle (L\to R)\in P}$ is a production rule, and ${\displaystyle \gamma ,\delta \in (N\cup \Sigma )^{*}}$ is the unaffected left and right part of the string, respectively. More generally, u is said to yield, or derive to, v, denoted as ${\displaystyle u\Rightarrow ^{*}v}$, if v can be obtained from u by repeated application of production rules, that is, if ${\displaystyle u=u_{0}\Rightarrow ...\Rightarrow u_{n}=v}$ for some n ≥ 0 and some strings ${\displaystyle u_{1},...,u_{n-1}\in (N\cup \Sigma )^{*}}$. In other words, the relation ${\displaystyle \Rightarrow ^{*}}$ is the reflexive transitive closure of the relation ${\displaystyle \Rightarrow }$.

The language of the grammar G is the set of all terminal-symbol strings derivable from its start symbol, formally: ${\displaystyle L(G)=\{w\in \Sigma ^{*}\mid S\Rightarrow ^{*}w\}}$. Derivations that do not end in a string composed of terminal symbols only are possible, but do not contribute to L(G).

Context-sensitive grammar

A formal grammar is context-sensitive if each rule in P is either of the form ${\displaystyle S\to \varepsilon }$ where ${\displaystyle \varepsilon }$ is the empty string, or of the form

αAβ → αγβ

with A ∈ N,^{[note 1]} ${\displaystyle \alpha ,\beta \in (N\cup \Sigma \setminus \{S\})^{*}}$,^{[note 2]} and ${\displaystyle \gamma \in (N\cup \Sigma \setminus \{S\})^{+}}$.^{[note 3]}

The name context-sensitive is explained by the α and β that form the context of A and determine whether A can be replaced with γ or not. By contrast, in a context-free grammar, no context is present: the left hand side of every production rule is just a nonterminal.

The string γ is not allowed to be empty. Without this restriction, the resulting grammars become equal in power to unrestricted grammars.^[10]

(Weakly) equivalent definitions

A noncontracting grammar is a grammar in which for any production rule, of the form u → v, the length of u is less than or equal to the length of v.

Every context-sensitive grammar is noncontracting, while every noncontracting grammar can be converted into an equivalent context-sensitive grammar; the two classes are weakly equivalent.^[12]

Some authors use the term context-sensitive grammar to refer to noncontracting grammars in general.

The left-context- and right-context-sensitive grammars are defined by restricting the rules to just the form αA → αγ and to just Aβ → γβ, respectively. The languages generated by these grammars are also the full class of context-sensitive languages.^[13] The equivalence was established by Penttonen normal form.^[14]

Examples

aⁿbⁿcⁿ

The following context-sensitive grammar, with start symbol S, generates the canonical non-context-free language { aⁿbⁿcⁿ | n ≥ 1 } :^{[citation needed]}

Rules 1 and 2 allow for blowing-up S to aⁿBC(BC)ⁿ⁻¹; rules 3 to 6 allow for successively exchanging each CB to BC (four rules are needed for that since a rule CB → BC wouldn't fit into the scheme αAβ → αγβ); rules 7–10 allow replacing a non-terminal B or C with its corresponding terminal b or c, respectively, provided it is in the right place. A generation chain for aaabbbccc is:

S

→₂ aSBC

→₂ aaSBCBC

→₁ aaaBCBCBC

→₃ aaaBCZCBC

→₄ aaaBWZCBC

→₅ aaaBWCCBC

→₆ aaaBBCCBC

→₃ aaaBBCCZC

→₄ aaaBBCWZC

→₅ aaaBBCWCC

→₆ aaaBBCBCC

→₃ aaaBBCZCC

→₄ aaaBBWZCC

→₅ aaaBBWCCC

→₆ aaaBBBCCC

→₇ aaabBBCCC

→₈ aaabbBCCC

→₈ aaabbbCCC

→₉ aaabbbcCC

→₁₀ aaabbbccC

→₁₀ aaabbbccc

aⁿbⁿcⁿdⁿ, etc.

More complicated grammars can be used to parse { aⁿbⁿcⁿdⁿ | n ≥ 1 }, and other languages with even more letters. Here we show a simpler approach using non-contracting grammars:^{[citation needed]} Start with a kernel of regular productions generating the sentential forms ${\displaystyle (ABCD)^{n}abcd}$ and then include the non contracting productions ${\displaystyle p_{Da}:Da\rightarrow aD}$, ${\displaystyle p_{Db}:Db\rightarrow bD}$, ${\displaystyle p_{Dc}:Dc\rightarrow cD}$, ${\displaystyle p_{Dd}:Dd\rightarrow dd}$, ${\displaystyle p_{Ca}}$Zdroj:https://en.wikipedia.org?pojem=Context-sensitive_grammar
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.