Content deleted Content added
m Reverted edits by 39.48.109.33 (talk) to last version by 199.111.152.83 |
mNo edit summary |
||
Line 47:
[[Regular language]]s are closed under string substitution. That is, if each letter of a regular language is substituted by another regular language, the result is still a regular language.<ref>Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.4, p.60</ref>
Similarly, [[context-free language]]s are closed under string substitution.<ref>Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.2, p.131</ref><ref group="note">Although every regular language is also context-free, the previous theorem is not implied by the current one, since the former yields a shaper result for regular languages.</ref>
A simple example is the conversion ''f''<sub>uc</sub>(.) to upper case, which may be defined e.g. as follows:
Line 80:
==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 letter is replaced by a single string. That is, ''f''(''a'')=''s'', where ''s'' is a string, for each letter ''a''.<ref group="note" name="singleton sets">Strictly formally, a homomorphism yields a language consisting of just one string, i.e. ''f''(''a'') = {''s''}.</ref><ref>Hopcroft, Ullman (1979), Sect.3.2, p.60-61</ref>
String homomorphisms are [[monoid morphism]]s on the [[free monoid]], preserving the [[binary operation]] of [[string concatenation]]. Given a language ''L'', the set ''f''(''L'') is called the '''homomorphic image''' of ''L''. The '''inverse homomorphic image''' of a string ''s'' is defined as
Line 101:
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 ''f''(''a'') ≠ ε for all ''a'' in the alphabet Σ. Simple single-letter [[substitution cipher]]s are examples of (ε-free) string homomorphisms.
Line 186:
:<math>\operatorname{Pref} (L) = \bigcup_{s\in L} \operatorname{Pref}_L(s) = \left\{ t\ \vert\ s=tu; s\in L; t,u\in \operatorname{Alph}(L)^* \right\}</math>
'''Example:''' <br />
<math>L=\left\{abc\right\}\mbox{ then } \operatorname{Pref}(L)=\left\{\varepsilon, a, ab, abc\right\}</math>
| |||