Processing...
Context-free multilanguages
1991-12-01
9301115 | cs.DS
This article is a sketch of ideas that were once intended to appear in the
author's famous series, "The Art of Computer Programming". He generalizes the
notion of a context-free language from a set to a multiset of words over an
alphabet. The idea is to keep track of the number of ways to parse a string.
For example, "fruit flies like a banana" can famously be parsed in two ways;
analogous examples in the setting of programming languages may yet be important
in the future.
The treatment is informal but essentially rigorous.