请输入您要查询的字词:

 

单词 RestrictedHomomorphism
释义

restricted homomorphism


Let h be a homomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath over an alphabet Σ. Let L be a languagePlanetmathPlanetmath over Σ. We say that h is k-restricted on L if

  1. 1.

    there is a letter bAlpha(L) such that no word in L begins with b and contains more than k-1 consecutive occurrences of b in it,

  2. 2.

    for any aAlpha(L),

    h(a)={λif a=baotherwise.

Here, Alpha(L) is the set of all letters in Σ that occur in words of L.

It is easy to see that any k-restricted homomorphism on L is a k-linear erasing on L, for if uL is a non-empty word, then we may write u=v1bm1v2bm2vnbmn, where each 0<mik-1, and each vi is a non-empty word not containing any occurrences of b. Then

|u|=|v1vn-1|+i=1nmi|h(u)|+n(k-1)|h(u)|+(k-1)|h(u)|=k|h(u)|.

Note that n|h(u)| since 1|vi| for each i=1,,n. A k-linear erasing is in general not a k-restricted homomorphism, an example of which is the following: L={a,ab}* and h:{a,b}{a,b} given by h(a)=a2 and h(b)=λ. Then h is a 1-linear erasing, but not a 1-restricted homomorphism, on L.

A family of languages is said to be closed underPlanetmathPlanetmath restricted homomorphism if for every L, and every k-restricted homomorphism h on L, h(L). By the previous paragraph, we see that if is closed under linear erasing, it is closed under restricted homomorphism. The converseMathworldPlanetmath of this is not necessarily true.

References

  • 1 A. Salomaa, Formal LanguagesMathworldPlanetmath, Academic Press, New York (1973).
随便看

 

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

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 18:53:09