snippetMinor
Is there a class of formal grammars that generate Recursive Languages only?
Viewed 0 times
languagesformalgrammarsgeneraterecursivethatthereclassonly
Problem
Is there a class of formal grammars that generate Recursive Languages only?
(ie with which it is not possible to generate non recursive languages.)
If so what kind of production rules/restrictions do they have?
And why are they not a part of Chomsky Hierarchy?
(ie with which it is not possible to generate non recursive languages.)
If so what kind of production rules/restrictions do they have?
And why are they not a part of Chomsky Hierarchy?
Solution
I cannot answer the question as asked, but here is what partial result I found,
which may interest you.
I will first address the following problem.
Is there a formal family of automata recognizing all and only recursive languages?
The answer to that question is no. This can be proved by diagonalization.
Suppose such a family F of automata, They can be enumerated as
integers like TM, and there is a F-universal Turing Machine U that can
simulate them given their integer representation. So given such an
automaton M and an input X, U(M,X) can tell wether X in in the
recursive language recognized by M, and always halt. Now, we modify U
into a machine U' that lies when X=M. Then consider the language
string X recognized by executing U'(X,X). By construction, the TM U'
will always halt with an answer (yes or no), thus recognizing a
recursive set. But it gives for any X an answer different from the one
given by automaton X. So the language recognized is different from any
of the languages recognized by the automata in the family F. So the
family F cannot recognize all recursive languages. This establishes
the result by contradiction.
However, this is not the question asked. The question is :
Is there a formal family of grammars generating all and only recursive languages?
This question is about a generative device rather than a
recognizer. Simulating a generative device will always halt and give
me an answer if a string is in the language. But it will tell me
nothing when a string is not in the language. Simulating generation
will just give a non-halting computation if used for recognition.
To do better, I would have to pair each grammar with the grammar for
the complement language, in which case I would have a recognizer, by
simulating both in parallel, being sure that one will find the input
string. But we have seen that such a recognizer cannot exist. So
pairing such grammars for complementarity is not possible.
Given such a grammar, we would know there is another one that is its
complement, but it would be undecidable whether any given one is the one generating the
complement language.
But I do not know at this point whether such a grammatical formalism can exist.
which may interest you.
I will first address the following problem.
Is there a formal family of automata recognizing all and only recursive languages?
The answer to that question is no. This can be proved by diagonalization.
Suppose such a family F of automata, They can be enumerated as
integers like TM, and there is a F-universal Turing Machine U that can
simulate them given their integer representation. So given such an
automaton M and an input X, U(M,X) can tell wether X in in the
recursive language recognized by M, and always halt. Now, we modify U
into a machine U' that lies when X=M. Then consider the language
string X recognized by executing U'(X,X). By construction, the TM U'
will always halt with an answer (yes or no), thus recognizing a
recursive set. But it gives for any X an answer different from the one
given by automaton X. So the language recognized is different from any
of the languages recognized by the automata in the family F. So the
family F cannot recognize all recursive languages. This establishes
the result by contradiction.
However, this is not the question asked. The question is :
Is there a formal family of grammars generating all and only recursive languages?
This question is about a generative device rather than a
recognizer. Simulating a generative device will always halt and give
me an answer if a string is in the language. But it will tell me
nothing when a string is not in the language. Simulating generation
will just give a non-halting computation if used for recognition.
To do better, I would have to pair each grammar with the grammar for
the complement language, in which case I would have a recognizer, by
simulating both in parallel, being sure that one will find the input
string. But we have seen that such a recognizer cannot exist. So
pairing such grammars for complementarity is not possible.
Given such a grammar, we would know there is another one that is its
complement, but it would be undecidable whether any given one is the one generating the
complement language.
But I do not know at this point whether such a grammatical formalism can exist.
Context
StackExchange Computer Science Q#31860, answer score: 2
Revisions (0)
No revisions yet.