MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's extend the unambiguity of language and grammar as follows: a language $L$ is unambiguous if there is a grammar that generates every word in $L$ in a unique way, the grammar may be of type 0 or any kind from type 0-3. A grammar $G$ is unambiguous if the grammar generates every word in a unique way, the grammar may be of type 0 or any kind from type 0-3.

Question:for any given language, is there a unambiguous grammar $G$?

share|cite|improve this question
If you used recursively-enumerable, context-sensitive, context-free and regular instead of type 0-3, it would be a lot easier to understand your question, as those terms are much more commonly used in language theory. – jmite Aug 2 '13 at 16:20
Certainly, this is not possible for any given language $L$, as there are languages which can't be expressed as a Turing Machine (and thus, not as a type 0 grammar). Every recursively-enumerable language can be accepted by a deterministic Turing machine, so if you could find an unambiguous unrestricted grammar to simulate a Turing machine, then every $RE$ language could be expressed this way. I don't know if such a thing is possible though. – jmite Aug 2 '13 at 16:26
As far as I can see, the straightforward way to simulate a deterministic TM by a grammar is indeed unambiguous, so the answer should be yes for every r.e. language. – Emil Jeřábek Aug 21 '13 at 12:34
@EmilJeřábek thank you. – XL _at_China Aug 22 '13 at 13:17
@jmite thank you. – XL _at_China Aug 22 '13 at 13:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.