Context-sensitive grammar

The context-sensitive grammars ( CSG short, of Engl. Context - sensitive grammar ) are a class of formal grammars and the same as the Type 1 grammars of the Chomsky hierarchy. They are characterized by the fact that some non-terminal symbols may only be replaced in a given context.

Definition

A context-sensitive grammar is a formal grammar with

  • Nonterminal symbols
  • Terminal symbols
  • Start symbol
  • Production rules of the form or the shape when:
  • Occurs on either the right side of a production rule

Description

With one exception, each production rule defined by the shape and.

This means that the nonterminal symbol is replaced in the context of strings and through. But while at least one symbol (terminal or nonterminal symbol) must exist, can be both empty. The following special cases are possible according to the definition:

In order to generate the empty word, allows you the rule, provided that there no right-hand side of a production rule.

Context-sensitive grammars, and monotone

The production rules of context-sensitive grammars not shorten the left side. Except for the rule so all the rules satisfy the condition. A context-sensitive grammar is therefore always a monotone grammar. But context-sensitive and monotonic grammars generate the same language class.

Some authors define context-sensitive grammars in the sense of monotone grammars. The production rules of the form are sometimes regarded as typical or canonical form of context-sensitive rules.

Normal Forms

For each context-sensitive grammar exists a grammar in Kuroda normal form of production rules of the form

A grammar in Kuroda normal form is generally true monotone but not context-sensitive.

A context-sensitive normal form is the one-sided normal form with rules of the kind:

There is a grammar in one-sided normal form for each context-sensitive grammar.

Alternative notation

In the field of linguistics to find an alternative notation of the production rules. It is the replacement rules similar to context-free rules and calls the context in which the rule must be applied at the right end of the rule:

Languages ​​generated by context-sensitive grammars

With the help of context-sensitive grammars can be exactly the context-sensitive languages ​​produce. This means that every context-sensitive grammar generates a context-sensitive language and to each context-sensitive language, there is a context-sensitive grammar that generates this language.

The context-sensitive languages ​​are exactly the languages ​​that can be recognized by a nondeterministic linear bounded Turing machine; that is, of a non-deterministic Turing machine whose tape is linearly bounded by the length of the input (ie there is a constant number so that the tape of the Turing machine has at most fields, the length of the input word is ).

That is why the word problem ( whether valid ) for context-sensitive languages ​​decidable.

Empty string Noncontracting grammar Kuroda-Normalform Determinism Word problem (computability)
485348
de