From Wikipedia Since there is a one-to-one correspondence between linear-bounded

Question

From Wikipedia

Since 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?

Explanation / Answer

The expression "one-to-one correspondence" seems a little too strong for me. It suggests that for every grammar there is a specific automaton. It should be read as: for every grammar an automaton can be constructed for the same language and vice-versa.

Context-sensitive languages are accepted by linear bounded automata and generated by context-sensitive grammars. Context-sensitive grammars have productions of the form ?A????? where A is a nonterminal and ? is nonempty. They are equivalent to length-increasing (more properly noncontracting, or monotone) grammars, which have the form ??? where |?|?|?| (usually ? is assumed to include at least one nonterminal).

The languages of Turing machines are generated by unrestricted, or type-0, grammars. See Chomsky Hierarchy.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.