n South African Computer Journal - A note on the generative capacity of random context : reviewed article
|Article Title||A note on the generative capacity of random context : reviewed article|
|© Publisher:||South African Computer Society (SAICSIT)|
|Journal||South African Computer Journal|
|Author||B. Atcheson, S. Ewert and D. Shell|
|Publication Date||Jun 2006|
|Pages||95 - 98|
|Keyword(s)||Dyck language, Formal languages, Random context and Regulated rewriting|
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...