En matemáticas e informática, una palabra mórfica o palabra sustitutiva es una secuencia infinita de símbolos que se construye a partir de una clase particular de endomorfismo de un monoide libre .
Sea f un endomorfismo del monoide libre A ∗ en un alfabeto A con la propiedad de que existe una letra a tal que f ( a ) = como para una cadena no vacía s : decimos que f es prolongable en a . La palabra
es una palabra pura mórfica o pura sustitución . Tenga en cuenta que es el límite de la secuencia a , f ( a ), f ( f ( a )), f ( f ( f ( a ))), ... Es claramente un punto fijo del endomorfismo f : el secuencia única que comienza con la letra a . [2] [3] En general, una palabra mórfica es la imagen de una palabra mórfica pura bajo una codificación, es decir, un morfismo que mapea letra a letra. [1]
Si una palabra mórfica se construye como el punto fijo de un k prolongable - morfismo uniforme en A ∗, entonces la palabra es k - automática . El n -ésimo término en tal secuencia puede ser producido por un autómata de estado finito leyendo los dígitos de n en base k . [1]
Un sistema D0L ( sistema Lindenmayer determinista libre de contexto ) viene dado por una palabra w del monoide libre A ∗ en un alfabeto A junto con un morfismo σ prolongable en w . El sistema genera la palabra D0L infinita ω = lim n → ∞ σ n ( w ). Las palabras puramente mórficas son palabras D0L pero no a la inversa. Sin embargo, si ω = u ν es una palabra D0L infinita con un segmento inicial u de longitud | u | ≥ | w |, entonces z ν es una palabra puramente mórfica, donde zes una carta no en una . [7]