4
$\begingroup$

I'm in an undergraduate class where we're studying formal grammars right now. I asked my teacher if there was any known set of rules for creating context free grammars that

  1. Was guaranteed to produce an unambiguous grammar.
  2. Allows for the creation of any possible unambiguous grammar.

I am well aware that determining whether a grammar is ambiguous is undecidable. I'm not sure if the above stated idea is reducible to that, but after fiddling around with it a bit, I couldn't think of a method for making such a reduction. That said I'm really no expert at reductions or grammars. I tried googling for a while, but I only found pages about undecidability. Does anyone know?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

No, and there is indeed a reduction to the undecidability of ambiguity.

First, note that ambiguity is (for context-free grammars) semi-decidable: just keep generating words by different left-derivations and say "ambiguous!" when you first find a word you've seen before.

Now, the method you are proposing allows to semi-decide unambiguity. You effectively look for a computable enumeration of all unambiguous grammars. You just generate grammars until you find your given grammar and answer "unambiguous!".

Since semi-decidability and co-semi-decidability imply decidability, this contradicts what you already know. Hence, there can be no "set of rules" as you propose.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! This is exactly what I was looking for. I can't upvote you because I don't have enough rep, but I wanted to note that this really helped me. $\endgroup$
    – sync
    Commented Feb 13, 2015 at 14:36

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.