3
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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 $\beta A \gamma \to \beta\alpha\gamma$ where $A$ is a nonterminal and $\alpha$ is nonempty. They are equivalent to length-increasing (more properly noncontracting, or monotone) grammars, which have the form $\alpha\to \beta$ where $|\alpha| \le |\beta|$ (usually $\alpha$ is assumed to include at least one nonterminal).

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

$\endgroup$
  • $\begingroup$ What is meant is that the relation between LBAs an CSGs is total. $\endgroup$ – reinierpost Jun 5 '14 at 8:43
  • $\begingroup$ By the way, that paragraph in Wikipedia contains several more errors - it should be fixed. $\endgroup$ – reinierpost Jun 5 '14 at 8:46
  • $\begingroup$ Thanks. What is the difference between "It suggests that for every grammar there is a specific automaton" and "It should be read as: for every grammar an automaton can be constructed for the same language"? $\endgroup$ – Tim Jun 5 '14 at 16:15
  • $\begingroup$ @Tim Yes, confusing. I mean the original formulation suggests a "unique" special natural automaton, whereas there might exist several suitable automata, depending on the algorithm you are using to constrict it. (It is like a many-to-many relation, and not a one-to-one.) $\endgroup$ – Hendrik Jan Jun 5 '14 at 19:37
2
$\begingroup$

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.

that wikipedia statement can be understood as that there is a 1-1 correspondence between unique LBAs and CSLs/CSGs. in other words every "unique" CSL has an LBA and vice versa but multiple LBAs can be equivalent (to the same CSL). in other words the same CSL can be "encoded" in different LBAs & CSGs. but note that determining equivalence of CSLs (as encoded eg as CSGs or LBAs) is undecidable.[1]

for your other question about TMs←→grammars conversions see [2] which also hints at both directions.

[1] Which properties of context sensitive languages are decidable?

[2] How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.