Síntese e análise de linguagens sensíveis ao contexto (Synthesis and Analysis of Context-Sensitive Languages)

César Alberto Bravo Pariente (cabpariente@uesc.br)1, Daniel Andersen Cerqueira Lima (daniel_lima@aol.com)1


1Universidade Estadual de Santa Cruz

This paper appears in: Revista IEEE América Latina

Publication Date: March 2016
Volume: 14,   Issue: 3 
ISSN: 1548-0992


Abstract:
Context-sensitive languages are usually omitted in undergraduate textbooks on Theory of Computation or studied only from structural point of view 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 can be fulfilled using standard techniques of formal languages. In particular it is 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}

Index Terms:
context-sensitive grammar, linear bounded automata, descriptional complexity, time complexity   


Documents that cite this document
This function is not implemented yet.


[PDF Full-Text (352)]