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.
- 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
|Date of creation||2013-03-22 18:57:09|
|Last modified on||2013-03-22 18:57:09|
|Last modified by||CWoo (3771)|