Time-bounded grammars and their languages

摘要

Formal grammars and formal languages are studied from the viewpoint of time-bounded grammars. A time-bound on a grammar is a measure of the “derivational complexity” of the language generated. Based on results of Gladkii [7] on connectivity in grammars, it is shown that a “linear speedup” can be obtained and that one can construct Turing acceptors to simulate grammars without loss of time. Positive containment and closure properties are also studied.