Content deleted Content added
m Fixing broken anchor: 2015-09-27 #Homomorphisms and e-free homomorphisms in formal language theory→Homomorphism#Formal language theory |
Reverted good faith edits by Dominus (talk): Not clearly improving |
||
| (3 intermediate revisions by 3 users not shown) | |||
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
while the inverse homomorphic image of a language <math>L</math> is defined as
<math>f^{-1}(L) = \{ s
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
==Right cancellation==
| |||