PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] context-sensitive language (Definition)

A context-sensitive language is a language over some alphabet generated by generated by some grammar known as a context-sensitive grammar.

Formally, a context-sensitive language is a formal grammar $ G=(\Sigma, N, P, \sigma)$ whose productions in $ P$ have the form

$\displaystyle aXb\to awb$
where $ X\in N$, $ a,b,w\in \Sigma^*$, and $ w\ne \lambda$, the empty word. Given a context-sensitive grammar $ G$, the context-sensitive language generated by $ G$ is $ L(G)$. In other words,
$\displaystyle L(G):=\lbrace v\in T^*\mid S\stackrel{*}{\to} v\rbrace,$
where $ T=\Sigma-N$ is the set of terminals, and $ \sigma\stackrel{*}{\to} v$ means that the word $ v$ over $ \Sigma$ is produced after a finite number of applications of the productions in $ P$ to $ \sigma$.

Remarks.

  1. The term “context-sensitive” means that any production $ aXb\to awb$ of $ G$, the non-terminal symbol $ X$ can only be transformed into the word $ w$ if $ X$ is surrounded by $ a$ and $ b$, or that $ X$ is in the “context” of $ aXb$. If in each production $ aXb\to awb$ of $ G$, $ a=b=\lambda$, (so that $ X$ no longer has a “context”), then $ G$ is a context-free grammar.
  2. It can be shown that $ G=(\Sigma, N, P, \sigma)$ is a context-sensitive grammar iff every production $ u\to v$ of $ P$ satisfies $ \vert u\vert\le \vert v\vert$, where $ \vert u\vert$ denotes the length of the word $ u$.
  3. The minimal automaton required for processing a context-sensitive languages is a bounded non-deterministic Turing machine.
  4. In the Chomsky hierarchy, context-sensitive grammars are at Level 1.



Anyone with an account can edit this entry. Please help improve it!

"context-sensitive language" is owned by CWoo. [ full author list (3) | owner history (2) ]
(view preamble)

View style:

See Also: context-free language

Also defines:  context-sensitive grammar, context-sensitive

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: level, Chomsky hierarchy, non-deterministic Turing machine, bounded, automaton, minimal, length, iff, context-free grammar, term, number, finite, terminals, empty word, productions, formal grammar, generated by, alphabet, language
There are 6 references to this entry.

This is version 11 of context-sensitive language, born on 2006-12-19, modified 2007-11-09.
Object id is 8644, canonical name is ContextSensitiveLanguage.
Accessed 1399 times total.

Classification:
AMS MSC: 68Q45 (Computer science :: Theory of computing :: Formal languages and automata)
 68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems)
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)