Context-free multilanguages
Abstract
Description
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.
Abstract added by Greg Kuperberg
Abstract added by Greg Kuperberg