Context sensitive grammar

from Wikipedia, the free encyclopedia

The context-sensitive grammars ( CSG for short , from English context-sensitive grammar ) are a class of formal grammars and are identical to the type 1 grammars of the Chomsky hierarchy . They are characterized by the fact that individual non-terminal symbols may only be replaced in a given context.

definition

A context sensitive grammar is a formal grammar with

  • a finite set (vocabulary),
  • Terminal symbols
  • Non-terminal symbols , including the
  • Start symbol
  • Production rules of the form or the form if the following applies:
    • does not appear on any right side of a production rule.

Some authors alternatively refer to the quadruple as grammar .

description

With one exception, every production rule has the form and by definition .

This means that the non-terminal symbol is replaced by and in the context of the character strings . But while a symbol (terminal or nonterminal symbol) consist of at least needs can, both as well be empty. The following special cases are therefore possible according to the definition:

In order to be able to generate the empty word , the rule is allowed , as long as there is no right-hand side of a production rule . By adding the empty word it is achieved that the context-sensitive languages ​​are a real superset of the context-free languages. Otherwise the result would be the situation, which is more difficult to describe, that only context-free grammars without empty-word productions are also context-sensitive grammars.

Context sensitive and monotonous grammars

The production rules of context-sensitive grammars do not shorten the left side. Except for the exception rule, all rules meet the condition . A context-sensitive grammar is therefore always a monotonous grammar (with the exception of the empty word production mentioned) . However, context-sensitive and monotonous grammars generate the same language class .

Some authors define context-sensitive grammars in terms of monotonous grammars. The production rules of form are sometimes only viewed as typical or canonical form of context-sensitive rules, as opposed to .

Normal forms

For every context-sensitive grammar there is a grammar in Kuroda normal form with production rules of the form

A grammar in Kuroda normal form is generally monotonous but no longer context-sensitive.

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

For every context-sensitive grammar there is a grammar in one-sided normal form.

Alternative notation

In the field of linguistics one finds an alternative notation of the production rules. The replacement rules are specified in a similar way to context-free rules and the context in which the rule can be used is stated at the right end of the rule:

Languages ​​generated from context-sensitive grammars

With the help of context-sensitive grammars, precisely the context-sensitive languages can be generated. That means: every context-sensitive grammar creates a context-sensitive language and for every context-sensitive language there is a context-sensitive grammar that creates this language.

The context-sensitive languages ​​are precisely those languages ​​that can be recognized by a nondeterministic , linearly restricted Turing machine ; d. i.e., from a nondeterministic Turing machine whose band is linearly bounded by the length of the input (i.e. there is a constant number such that the band of the Turing machine has at most fields, where the length of the input word is).

Why is the word problem (whether true) for context-sensitive languages decidable .

Individual evidence

  1. for example Uwe Schöning : Theoretical Computer Science - in brief . 5th edition. Spektrum Akademischer Verlag, 2008, ISBN 978-3-8274-1824-1 , section 1.1.2, p. 9 .
  2. ^ Klaus W. Wagner: Theoretical Computer Science: A compact introduction . Springer, 2003, ISBN 978-3-540-01313-6 , Chapter 6, pp. 187 ( limited preview in Google Book search).
  3. M. Penttonen, One-Sided and Two-Sided Context in Formal Grammars , Information and Control, 25 (1974) 371-392
  4. see also Rozenberg and Salomaa, Handbook of Formal Languages , p. 190
  5. ^ Daniel Jurafsky, James H. Martin: Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition . Prentice Hall, 2009, ISBN 978-0-13-187321-6 , Chapter 16, pp. 531 ( limited preview in Google Book search).

literature

  • Grzegorz Rozenberg, Arto Salomaa: Handbook of Formal Languages. Volume 1: Word, Language, Grammar . Springer, Berlin et al. 1997, ISBN 3-540-60420-0 ( limited preview in the Google book search).
  • Katrin Erk, Lutz Priese: Theoretical Computer Science: A Comprehensive Introduction . 3rd expanded edition. Springer, Berlin et al. 2008, ISBN 978-3-540-76319-2 ( limited preview in the Google book search).