Say you have a (context-free) grammar, and you wish to mathematically model the magnitude of the ambiguity possible under this grammar, across the space of all possible** input strings.

Practically, one can feed in a large number of inputs strings to a parser of the grammar, and get a distribution over that set of inputs. This may be useful if one assumes the set of inputs to somehow represent a more general case, but for the sake of exercise, let us arbitrarily assume, that this approach does not generalize, or that we cannot a-priori come up with a sufficiently representative set of strings.

Can you suggest a mathematical model for the magnitude of ambiguity allowed by a given grammar? differently phrased, how would you creatively model the combinatorial magnitude of possible parses?

** this is of course ill-defined, but it takes some creativity to come up with a definition for "reasonable" input strings, or think of a measure for the length or complexity of a string, that can serve as a useful parameter in the model.

  • $\begingroup$ Are you after a definition, or an algorithm that actually computes the value? (Depending on the definition, I suspect the latter may not be computable. Gut feeling.) $\endgroup$
    – Raphael
    Aug 31, 2017 at 17:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.