String operations: Difference between revisions

Revision as of 15:57, 7 December 2017

Revision as of 09:20, 24 March 2018

Line 78:

==String homomorphism==

A '''string homomorphism''' (often referred to simply as a [[Homomorphism#Homomorphisms and e-free homomorphisms in 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

:''f''<sup>−1</supmath>f^{-1}(''s'') = \{ ''w'' | ''f''(''w'') = ''s'' \}</math>

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

:''f''<sup>−1</supmath>f^{-1}(''L'') = \{ ''s'' | ''f''(''s'') ∈\in ''L'' \}</math>

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

<math>f(f^{-1}(L)) \subseteq L</math>

:''f''(''f''⁻¹(''L'')) ⊆ ''L''

and

<math>L \subseteq f^{-1}(f(L))</math>

:''L'' ⊆ ''f''⁻¹(''f''(''L''))

for any language ''<math>L''</math>.

The class of regular languages is closed under homomorphisms and inverse homomorphisms.<ref>Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.5, p.61</ref>

Similarly, the context-free languages are closed under homomorphisms<ref group="note">This follows from the [[#String substitution|above-mentioned]] closure under arbitrary substitutions.</ref> and inverse homomorphisms.<ref>Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.3, p.132</ref>

A string homomorphism is said to be ε-free (or e-free) if ''<math>f''(''a'') ≠\neq ε\varepsilon</math> for all ''a'' in the alphabet Σ<math>\Sigma</math>. Simple single-letter [[substitution cipher]]s are examples of (ε-free) string homomorphisms.

An example string homomorphism ''g''_uc can also be obtained by defining similar to the [[#String_substitution|above]] substitution: ''g''_uc(‹a›) = ‹A›, ..., ''g''_uc(‹0›) = ε, but letting ''g''_uc undefined on punctuation chars.