请输入您要查询的字词:

 

单词 MetalinearLanguage
释义

metalinear language


Recall that a linear grammar is a formal grammar G=(Σ,N,P,σ) whose productions are of the form Ax, where A is a terminal symbol, and x is a word over Σ, with at most one occurrence of a non-terminal symbol.

The conceptMathworldPlanetmath of a linear grammar can be generalized: define a k-linear grammar as a formal grammar G=(Σ,N,P,σ) such that every production in P has one of the three following forms:

  • Au,

  • AuBv,

  • σW,

where A,B are non-terminal symbols, u,v are terminal words, and W is a word over Σ with no more than k occurrences of non-terminal symbols, and none of which is the start symbol σ. Any k-linear grammar is context-free.

A languagePlanetmathPlanetmath is said to be k-linear if it can be generated by a k-linear grammar. Note that a language is 1-linear iff it is linear.

A language is said to be metalinear if it is k-linear for some positive integer k. In other words, if (k) denotes the family of k-linear languages, then the family () of metalinear langauges is

()={(k)k1}.

It is easy to see we have the following inclusions

(k)(k)()

where and are the families of regularPlanetmathPlanetmath 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).

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 2:42:37