String operations: Difference between revisions

Revision as of 22:49, 20 September 2023

Revision as of 00:51, 11 November 2023

Line 78:

==String homomorphism==

A '''string homomorphism''' (often referred to simply as a [[Homomorphism#Homomorphisms and e-free homomorphisms in formalFormal language theory|homomorphism]] in [[formal language theory]]) is a string substitution such that each character is replaced by a single string. That is, <math>f(a)=s</math>, where <math>s</math> is a string, for each character <math>a</math>.<ref group="note" name="singleton sets">Strictly formally, a homomorphism yields a language consisting of just one string, i.e. <math>f(a) = {s}</math>.</ref><ref>Hopcroft, Ullman (1979), Sect.3.2, p.60-61</ref>

String homomorphisms are [[monoid morphism]]s on the [[free monoid]], preserving the empty string and the [[binary operation]] of [[string concatenation]]. Given a language <math>L</math>, the set <math>f(L)</math> is called the '''homomorphic image''' of <math>L</math>. The '''inverse homomorphic image''' of a string <math>s</math> is defined as