patternMinor
Correspondence between automata and formal grammars?
Viewed 0 times
formalautomatagrammarsbetweencorrespondenceand
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#26428, answer score: 7
Revisions (0)
No revisions yet.