context-sensitive language
A context-sensitive language is a language over some alphabet generated by generated by some known as a context-sensitive grammar.
Formally, a context-sensitive language is a formal grammar , such that given any production in , it
- 1.
-
2.
or is , provided that the start symbol does not occur on the right side of any productions in .
In other words, if does not contain the production , then any production will have the form in condition 1. On the other hand, if does contain , then for any production of , does not occur in .
The reason for including the second condition is to ensure the possibility that may be generated by the grammar.
One may interpret the first condition as follows: the non-terminal symbol can only be transformed into the word if it is surrounded by and , or that it is in the “context” of . If in each production of , , (so that no longer has a “context”), then is a context-free grammar.
Given a context-sensitive grammar , the context-sensitive language generated by is . In other words,
where is the set of terminals, and means that the word over is produced after a finite number of applications of the productions in to .
With condition 2, we see that a context-sensitive language contains iff it is generated by a context-sensitive grammar containing . With condition 2, every context-free language is context-sensitive. Without condition 2, every -free context-free language is -free context-sensitive.
and are examples of context-sensitive languages that are not context-free, the second of which is -free.
Remarks.
-
1.
A formal grammar is said to be length-increasing if for every production of , the length of is at most the length of : . Every context-sensitive grammar not containing (condition 2) is length-increasing. Conversely, any language generated by a length-increasing grammar is context-sensitive.
-
2.
The minimal automaton required for processing a context-sensitive languages is a bounded non-deterministic Turing machine (bounded linear automaton).
-
3.
The family of context-sensitive languages has the following closure properties: union, intersection, concatenation, Kleene star, reversal, and complementation (proved in 1988). It is not closed under homomorphism.
-
4.
In the Chomsky hierarchy, context-sensitive grammars are at Level 1. In fact, every context-sensitive language is recursive. The converse is not true, however.
-
5.
Given a context-sensitive language and a word , it is decidable whether .
References
- 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
- 2 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, (1969).
Title | context-sensitive language |
Canonical name | ContextsensitiveLanguage |
Date of creation | 2013-03-22 16:28:40 |
Last modified on | 2013-03-22 16:28:40 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 23 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 68Q42 |
Classification | msc 68Q45 |
Synonym | type-1 language |
Synonym | type-1 grammar |
Related topic | ContextFreeLanguage |
Related topic | LinearBoundedAutomaton |
Defines | context-sensitive grammar |
Defines | context-sensitive |
Defines | length-increasing |