The Linear-Bounded Automata (LBA) was developed as models for actual computers rather than for the analysis of computational processes. An LBA is a space-bounded Turing machine, where for its computation it cannot consume space more than the size of original input. An LBA decides the language strings for accept/reject unlike the Turing machine which recognizes the language strings. The LBA decides regular languages, context-free languages, and context-sensitive languages. When compared with other two machines, i.e., Finite Automata and Pushdown Automata, the LBA accepts all recursive languages (decidable languages). In addition to LBA, this chapter presents the analysis of some decidable languages having theoretical significance: the language of all regular expressions, empty language, language of DFA pairs, and the language of grammar-and-strings pairs. The chapter also covers topics like, some non-closure properties of context-free languages, context-sensitive languages and grammars, standard and extended Chomsky-hierarchy, decidable and closure properties of context-sensitive languages. In addition, the topics that are not so common but provides a foundation for advanced studies, have been also covered, like, indexed grammars, regulated rewriting grammars, programmed grammars, matrix grammars, conjunctive grammars, and at the end, an analysis has been given about universal versus Chomskian grammars, followed with self review questions and exercises.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Linear-Bounded Automata and Context-Sensitive Languages

  • K. R. Chowdhary

摘要

The Linear-Bounded Automata (LBA) was developed as models for actual computers rather than for the analysis of computational processes. An LBA is a space-bounded Turing machine, where for its computation it cannot consume space more than the size of original input. An LBA decides the language strings for accept/reject unlike the Turing machine which recognizes the language strings. The LBA decides regular languages, context-free languages, and context-sensitive languages. When compared with other two machines, i.e., Finite Automata and Pushdown Automata, the LBA accepts all recursive languages (decidable languages). In addition to LBA, this chapter presents the analysis of some decidable languages having theoretical significance: the language of all regular expressions, empty language, language of DFA pairs, and the language of grammar-and-strings pairs. The chapter also covers topics like, some non-closure properties of context-free languages, context-sensitive languages and grammars, standard and extended Chomsky-hierarchy, decidable and closure properties of context-sensitive languages. In addition, the topics that are not so common but provides a foundation for advanced studies, have been also covered, like, indexed grammars, regulated rewriting grammars, programmed grammars, matrix grammars, conjunctive grammars, and at the end, an analysis has been given about universal versus Chomskian grammars, followed with self review questions and exercises.