12
$\begingroup$

Turing machines and unrestricted grammars are two different formalisms that define the RE languages. Some RE languages are decidable, but not all are.

We can define the decidable languages with Turing machines by saying that a language is decidable iff there is a TM for the language that halts and accepts all strings in the language and halts and rejects all strings not in the language. My question is this: is there an analogous definition of decidable languages based on unrestricted grammars rather than Turing machines?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
7
$\begingroup$

A language is decidable, iff it is semi-decidable and its complement is semi-decidable. Moreover, a language is recursive-enumerable iff it is semi-decidable and thus you can find an unrestricted Grammar. Therfore:

A language $L$ is decidable iff there is both an unrestricted Grammar $G$ with $L(G) = L$ and an unrestricted Grammar $\bar G$ with $L(\bar G) = \bar L$.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ Also, aren't "semi-decidable" and "recursively enumerable" synonyms? $\endgroup$
    – templatetypedef
    Commented Feb 26, 2013 at 18:18
  • 1
    $\begingroup$ 1. IIRC there is no known class of formal grammars corresponding to decidable languages, so i don't think this is possible with a single unrestricted grammar. 2. Yes, they happen to mean the same. $\endgroup$
    – Simon S
    Commented Feb 26, 2013 at 18:47
  • 1
    $\begingroup$ You are mistaken about the definition of decidability. Decidable means "there is a Turing machine which computes the answer". The relation you quote as the definition is in fact a theorem, which I have heard attributed to Emile Post. $\endgroup$
    – Andrej Bauer
    Commented Feb 26, 2013 at 23:01
  • 2
    $\begingroup$ Next, semidecidability and recursive enumerability are not synonyms, but they are equivalent notions. A set is semidecidable if it is the halting set of a Turing machine, while it is recursively enumerable if it is enumerated by a Turing machine. $\endgroup$
    – Andrej Bauer
    Commented Feb 26, 2013 at 23:03
  • 1
    $\begingroup$ 1. You are right, decidability isn't necessarily defined that way (but can be), and therefore I edited the answer. 2. Thats why i wrote "they happen to mean the same", perhaps "synonym" is the wrong word. $\endgroup$
    – Simon S
    Commented Feb 27, 2013 at 10:27
2
$\begingroup$

There can not be a useful class of grammars for $\mathrm{R}$ (the set of recursive languages), since

  • every useful class of grammars is enumerable, and
  • $\mathrm{R}$ is not semi-decidable or, equivalently, not enumerable.

The first is obviously not a rigorous theorem (and can't be), it's just judgemental conjecture. The set of all grammars is enumerable, and any restriction that is not decidable is likely not very useful¹ in itself; in particular it won't be a syntactic restriction (like Chomsky's).

The second is formally true, see also here.

  1. Of course, people have defined such restrictions, and those classes have their uses, but it is even hard to see whether a given grammar falls into simpler subclasses.
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Why doesn't this argument also apply to Turing machines? There is a useful class of TMs for R (the deciders) even though they aren't enumerable. $\endgroup$
    – templatetypedef
    Commented Feb 27, 2013 at 17:15
  • $\begingroup$ @templatetypedef: The thought crossed my mind. 1) The set of Turing machines for R is somewhat "intangible". Arguably, it is not "useful" in any but the most theoretical sense. 2) The TM is an operative model, whereas grammars are more of a declarative (if generative) model. Therefore, it is unlikely that even a property as "useless" as the one of R-TMs exists. (Again, this is all intuition-based babbling.) $\endgroup$
    – Raphael
    Commented Feb 28, 2013 at 8:09
2
$\begingroup$

This question is addressed in a paper by Henning Fernau from 1994. Henning states:

As an example, we consider the family of recursive languages. It is an open question whether there is a 'natural' grammatical characterization of this language class. As we will show in the following, any grammar family characterizing the recursive languages must have some strange properties.

We direct the reader who is curious to learn about those strange properties to the paper.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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