String operations: Difference between revisions

Revision as of 20:45, 18 November 2017

Revision as of 15:57, 7 December 2017

Line 44:

for string ''s'' ∈ ''L'' and character ''a'' ∈ Σ. String substitutions may be extended to entire languages as <ref>Hopcroft, Ullman (1979), Sect.3.2, p.60</ref>

:<math>f(L)=\bigcup_{s\in L} f(s)</math>

[[Regular language]]s are closed under string substitution. That is, if each character in the alphabet 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>

Line 78:

==String homomorphism==

A '''string homomorphism''' (often referred to simply as a [[Homomorphism#Homomorphisms_and_eHomomorphisms and e-free_homomorphisms_in_formal_language_theoryfree 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, ''f''(''a'')=''s'', where ''s'' is a string, for each character ''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 empty string and 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

:''f''⁻¹(''s'') = { ''w'' | ''f''(''w'') = ''s'' }

while the inverse homomorphic image of a language ''L'' is defined as

:''f''⁻¹(''L'') = { ''s'' | ''f''(''s'') ∈ ''L'' }

In general, ''f''(''f''⁻¹(''L'')) ≠ ''L'', while one does have

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

and

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

Line 124:

\end{cases}</math>

Here <math>\varepsilon</math> denotes the [[empty string]]. The projection of a string is essentially the same as a [[projection in relational algebra]].

String projection may be promoted to the '''projection of a language'''. Given a [[formal language]] ''L'', its projection is given by

:<math>\pi_\Sigma (L)=\{\pi_\Sigma(s)\ \vert\ s\in L \}</math>{{cncitation needed|date=August 2017}}

==Right quotient==

Line 143:

:<math>\varepsilon / a = \varepsilon</math>

Similarly, given a subset <math>S\subset M</math> of a monoid <math>M</math>, one may define the quotient subset as

:<math>S/a=\{s\in M\ \vert\ sa\in S\}</math>

Left quotients may be defined similarly, with operations taking place on the left of a string.{{cncitation needed|date=August 2017}}

Hopcroft and Ullman (1979) define the quotient ''L''₁/''L''₂ of the languages ''L''₁ and ''L''₂ over the same alphabet as ''L''₁/''L''₂ = { ''s'' | ∃''t''∈''L''₂. ''st''∈''L''₁ }.<ref>Hopcroft, Ullman (1979), Sect.3.2, p.62</ref>

This is not a generalization of the above definition, since, for a string ''s'' and distinct characters ''a'', ''b'', Hopcroft's and Ullman's definition implies {''sa''} / {''b''} yielding {}, rather than { ε }.

The left quotient (when definied similar to Hopcroft and Ullman 1979) of a singleton language ''L''₁ and an arbitrary language ''L''₂ is known as [[Brzozowski derivative]]; if ''L''₂ is represented by a [[regular expression]], so can be the left quotient.<ref>{{cite journal| author=Janusz A. Brzozowski| authorlink=Janusz Brzozowski (computer scientist)|title=Derivatives of Regular Expressions| journal=JACMJ ACM| year=1964| volume=11| pages=481–494| doi=10.1145/321239.321249}}</ref>

==Syntactic relation==

Line 163:

:<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.{{cncitation needed|date=August 2017}}

==Right cancellation==

Line 179:

Clearly, right cancellation and projection [[Commutative property|commute]]:

:<math>\pi_\Sigma(s)\div a = \pi_\Sigma(s \div a )</math>{{cncitation needed|date=August 2017}}

==Prefixes==

Line 186:

:<math>\operatorname{Pref}_L(s) = \{t\ \vert\ s=tu \mbox { for } t,u\in \operatorname{Alph}(L)^*\}</math>

where <math>s\in L</math>.

The '''prefix closure of a language''' is

:<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>

Line 195:

<math>L=\left\{abc\right\}\mbox{ then } \operatorname{Pref}(L)=\left\{\varepsilon, a, ab, abc\right\}</math>

A language is called '''prefix closed''' if <math>\operatorname{Pref} (L) = L</math>.

The prefix closure operator is [[idempotent]]:

Line 201:

:<math>\operatorname{Pref} (\operatorname{Pref} (L)) =\operatorname{Pref} (L)</math>

The '''prefix relation''' is a [[binary relation]] <math>\sqsubseteq</math> such that <math>s\sqsubseteq t </math> if and only if <math>s \in \operatorname{Pref}_L(t)</math>. This relation is a particular example of a [[prefix order]].{{cncitation needed|date=August 2017}}

==See also ==