From WikipediaSince there is a one-to-one correspondence between linear-bounded  automata and such grammars, no more tape than that occupied by the  original string is necessary for the string to be recognized by the  automaton.Note: If I am correct, such grammars mean context-sensitive grammars.I wonder if the quote means that:a context-sensitive language can have multiple  context-sensitive grammars that can generate it, and multiple linearly bounded machines that can have it as their recognized languages, and there exists a one-to-one correspondence between the linearly bounded machines and the context-sensitive grammars, for the context-sensitive language. More generally, a recursively enumerable formal language can have multiple formal grammars that can generate it, and multiple Turing machines that can have it as their recognized languages. So I wonder if there exists a one-to-one correspondence between Turing machines and formal grammars, for a recursively enumerable formal language. Given a formal grammar, how can we construct a Turing machine to have the language generated by the grammar as its recognized language?Conversely, given a Turing machine, how can we construct a formal grammar which can generate the language which is the one recongized by the Turing machine?
Correspondence between automata and formal grammars?
formal languages;terminology;automata;formal grammars