metalinear language
Recall that a linear grammar is a formal grammar whose productions are of the form , where is a terminal symbol, and is a word over , with at most one occurrence of a non-terminal symbol.
The concept of a linear grammar can be generalized: define a -linear grammar as a formal grammar such that every production in has one of the three following forms:
-
•
,
-
•
,
-
•
,
where are non-terminal symbols, are terminal words, and is a word over with no more than occurrences of non-terminal symbols, and none of which is the start symbol . Any -linear grammar is context-free.
A language is said to be -linear if it can be generated by a -linear grammar. Note that a language is -linear iff it is linear.
A language is said to be metalinear if it is -linear for some positive integer . In other words, if denotes the family of -linear languages, then the family of metalinear langauges is
It is easy to see we have the following inclusions
where and are the families of regular and context-free languages respectively.
In fact, it can be shown that all of the inclusions above are strict, providing us with an infinite chain of families of languages between the regular languages and the context-free languages.
References
- 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
Title | metalinear language |
---|---|
Canonical name | MetalinearLanguage |
Date of creation | 2013-03-22 18:57:09 |
Last modified on | 2013-03-22 18:57:09 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 8 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 68Q45 |
Classification | msc 68Q70 |
Related topic | LinearGrammar |
Related topic | LinearLanguage |
Defines | -linear language |