String operations: Difference between revisions

Revision as of 00:51, 11 November 2023

Revision as of 01:02, 18 June 2024

Line 78:

==String homomorphism==

A '''string homomorphism''' (often referred to simply as a [[Homomorphism#Formal 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