String operations: Difference between revisions

Revision as of 22:49, 20 September 2023

Latest revision as of 15:18, 12 May 2025

(4 intermediate revisions by 4 users not shown)

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

<math>f^{-1}(s) = \{ w |\mid f(w) = s \}</math>

while the inverse homomorphic image of a language <math>L</math> is defined as

<math>f^{-1}(L) = \{ s |\mid f(s) \in L \}</math>

In general, <math>f(f^{-1}(L)) \neq L</math>, while one does have

Line 160:

:<math>\{S/m\ \vert\ m\in M\}</math>

is finite. In the case that ''M'' is the monoid of words over some alphabet, ''S'' is then a [[regular language]], that is, a language that can be recognized by a [[finite -state automaton]]. This is discussed in greater detail in the article on [[syntactic monoid]]s.{{citation needed|date=August 2017}}

==Right cancellation==