PROJECT TITLE :

Synthesis and Analysis of Context-Sensitive Languages

ABSTRACT:

Context-sensitive languages are sometimes omitted in undergraduate textbooks on Theory of Computation or studied only from structural purpose of read in graduate textbooks with very few classical examples and no techniques of design of context-sensitive grammars and their corresponding linear bounded automata. Here we present a case of study showing that such omission and lack of examples and techniques will be fulfilled using normal techniques of formal languages. In specific it's stablished the descriptional and time complexity of an ambiguous context-sensitive grammar and a deterministic linear bounded automaton for the context-sensitive language L = a^mb^nc^mn : m, n >= 1