String operations: Difference between revisions

Revision as of 17:50, 30 August 2017

Revision as of 18:10, 30 August 2017

Line 128:

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>{{cn|date=August 2017}}

==Right quotient==

Line 157:

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

==Right cancellation==

Line 173:

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

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

==Prefixes==

Line 195:

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

==See also ==