n South African Computer Journal - A note on the generative capacity of random context : reviewed article




Context-free languages are well studied, but of limited practical use due to their simplicity. Context-sensitive languages on the other hand provide more than enough power for compiler construction, but are difficult to use precisely because of this. Random context languages fall within the gap between these two types and make a trade-off between expressivity and ease-of-use.

To select the most appropriate grammar class for a task it helps to know which languages it can and cannot generate. Examples of languages beyond the generative power of a grammar class give one a sense of what is being traded away when selecting a simpler type. These examples are also of theoretical interest for probing the limits of formal languages.
Although it has been shown that one must exist, to date there is no known example of a language that may be generated by a context-sensitive grammar but not by a random context grammar. This paper considers one language conjectured in the literature to fall within this gap and shows that it does not in fact do so, by giving a random context grammar capable of generating it.


Article metrics loading...

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error