Контекстке сезімтал грамматика түрлері

Type of a formal grammar
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. 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 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. The syntaxes of some visual programming languages can be described by context sensitive graph grammars.

Let us notate a formal grammar as , with a set of nonterminal symbols, a set of terminal symbols, a set of production rules, and the start symbol. A string directly yields, or directly derives to, a string , denoted as , if v can be obtained from u by an application of some production rule in P, that is, if and , where is a production rule, and is the unaffected left and right part of the string, respectively. More generally, u is said to yield, or derive to, v, denoted as , if v can be obtained from u by repeated application of production rules, that is, if for some n ≥ 0 and some strings In other words, the relation is the reflexive transitive closure of the relation
The language of the grammar G is the set of all terminal symbol strings derivable from its start symbol, formally: Derivations that do not end in a string composed of terminal symbols only are possible, but do not contribute to L(G).

A noncontracting grammar for the language { a2i | i ≥ 1 } is constructed in Example 9.5 (p. 224) of (Hopcroft, Ullman, 1979):

Every context sensitive grammar which does not generate the empty string can be transformed into a weakly equivalent one in Kuroda normal form. "Weakly equivalent" here means that the two grammars generate the same language. The normal form will not in general be context sensitive, but will be a noncontracting grammar. The Kuroda normal form is an actual normal form for non contracting grammars.

A formal language can be described by a context sensitive grammar if and only if it is accepted by some linear bounded automaton (LBA). In some textbooks this result is attributed solely to Landweber and Kuroda. (Myhill introduced the concept of deterministic LBA in 1960. Peter S. Landweber published in 1963 that the language accepted by a deterministic LBA is context sensitive. Kuroda introduced the notion of non deterministic LBA and the equivalence between LBA and CSGs in 1964.) as of 2010 it is still an open question whether every context sensitive language can be accepted by a deterministic LBA.

Context sensitive languages are closed under complement. This 1988 result is known as the Immerman–Szelepcsényi theorem. inverse homomorphism, and Kleene plus. Every recursively enumerable language L can be written as h(L) for some context sensitive language L and some string homomorphism h.

The decision problem that asks whether a certain string s belongs to the language of a given context sensitive grammar G, is PSPACE complete. Moreover, there are context sensitive grammars whose languages are PSPACE complete. In other words, there is a context sensitive grammar G such that deciding whether a certain string s belongs to the language of G is PSPACE complete (so G is fixed and only s is part of the input of the problem). The emptiness problem for context sensitive grammars (given a context sensitive grammar G, is L(G)=∅ ?) is undecidable.

Savitch has proven the following theoretical result, on which he bases his criticism of CSGs as basis for natural language: for any recursively enumerable set R, there exists a context sensitive language/grammar G which can be used as a sort of proxy to test membership in R in the following way: given a string s, s is in R if and only if there exists a positive integer n for which scn is in G, where c is an arbitrary symbol not part of R.

Ongoing research on computational linguistics has focused on formulating other classes of languages that are "mildly context sensitive" whose decision problems are feasible, such as tree adjoining grammars, combinatory categorial grammars, coupled context free languages, and linear context free rewriting systems. The languages generated by these formalisms properly lie between the context free and context sensitive languages. More recently, the class PTIME has been identified with range concatenation grammars, which are now considered to be the most expressive of the mild context sensitive language classes.