String operations

<h2 id="strings-and-languages">Strings and languages</h2>
A string is a finite sequence of characters.
The <a href="/facts/Empty_string/T7udJlmQ">empty string</a> is denoted by 
 
 
 
 ε
 
 
 {\displaystyle \varepsilon }
 
.
The concatenation of two string 
 
 
 
 s
 
 
 {\displaystyle s}
 
 and 
 
 
 
 t
 
 
 {\displaystyle t}
 
 is denoted by 
 
 
 
 s
 ⋅
 t
 
 
 {\displaystyle s\cdot t}
 
, or shorter by 
 
 
 
 s
 t
 
 
 {\displaystyle st}
 
.
Concatenating with the empty string makes no difference: 
 
 
 
 s
 ⋅
 ε
 =
 s
 =
 ε
 ⋅
 s
 
 
 {\displaystyle s\cdot \varepsilon =s=\varepsilon \cdot s}
 
.
Concatenation of strings is <a href="/facts/Associative/EQX8lV6r">associative</a>: 
 
 
 
 s
 ⋅
 (
 t
 ⋅
 u
 )
 =
 (
 s
 ⋅
 t
 )
 ⋅
 u
 
 
 {\displaystyle s\cdot (t\cdot u)=(s\cdot t)\cdot u}
 
.
For example, 
 
 
 
 (
 ⟨
 b
 ⟩
 ⋅
 ⟨
 l
 ⟩
 )
 ⋅
 (
 ε
 ⋅
 ⟨
 a
 h
 ⟩
 )
 =
 ⟨
 b
 l
 ⟩
 ⋅
 ⟨
 a
 h
 ⟩
 =
 ⟨
 b
 l
 a
 h
 ⟩
 
 
 {\displaystyle (\langle b\rangle \cdot \langle l\rangle )\cdot (\varepsilon \cdot \langle ah\rangle )=\langle bl\rangle \cdot \langle ah\rangle =\langle blah\rangle }
 
.
A <a href="/facts/Language_(computer_science)/crDTyP8q">language</a> is a finite or infinite set of strings.
Besides the usual set operations like union, intersection etc., concatenation can be applied to languages:
if both 
 
 
 
 S
 
 
 {\displaystyle S}
 
 and 
 
 
 
 T
 
 
 {\displaystyle T}
 
 are languages, their concatenation 
 
 
 
 S
 ⋅
 T
 
 
 {\displaystyle S\cdot T}
 
 is defined as the set of concatenations of any string from 
 
 
 
 S
 
 
 {\displaystyle S}
 
 and any string from 
 
 
 
 T
 
 
 {\displaystyle T}
 
, formally 
 
 
 
 S
 ⋅
 T
 =
 {
 s
 ⋅
 t
 ∣
 s
 ∈
 S
 ∧
 t
 ∈
 T
 }
 
 
 {\displaystyle S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}}
 
.
Again, the concatenation dot 
 
 
 
 ⋅
 
 
 {\displaystyle \cdot }
 
 is often omitted for brevity.
The language 
 
 
 
 {
 ε
 }
 
 
 {\displaystyle \{\varepsilon \}}
 
 consisting of just the empty string is to be distinguished from the empty language 
 
 
 
 {
 }
 
 
 {\displaystyle \{\}}
 
.
Concatenating any language with the former doesn't make any change: 
 
 
 
 S
 ⋅
 {
 ε
 }
 =
 S
 =
 {
 ε
 }
 ⋅
 S
 
 
 {\displaystyle S\cdot \{\varepsilon \}=S=\{\varepsilon \}\cdot S}
 
,
while concatenating with the latter always yields the empty language: 
 
 
 
 S
 ⋅
 {
 }
 =
 {
 }
 =
 {
 }
 ⋅
 S
 
 
 {\displaystyle S\cdot \{\}=\{\}=\{\}\cdot S}
 
.
Concatenation of languages is associative: 
 
 
 
 S
 ⋅
 (
 T
 ⋅
 U
 )
 =
 (
 S
 ⋅
 T
 )
 ⋅
 U
 
 
 {\displaystyle S\cdot (T\cdot U)=(S\cdot T)\cdot U}
 
.
For example, abbreviating 
 
 
 
 D
 =
 {
 ⟨
 0
 ⟩
 ,
 ⟨
 1
 ⟩
 ,
 ⟨
 2
 ⟩
 ,
 ⟨
 3
 ⟩
 ,
 ⟨
 4
 ⟩
 ,
 ⟨
 5
 ⟩
 ,
 ⟨
 6
 ⟩
 ,
 ⟨
 7
 ⟩
 ,
 ⟨
 8
 ⟩
 ,
 ⟨
 9
 ⟩
 }
 
 
 {\displaystyle D=\{\langle 0\rangle ,\langle 1\rangle ,\langle 2\rangle ,\langle 3\rangle ,\langle 4\rangle ,\langle 5\rangle ,\langle 6\rangle ,\langle 7\rangle ,\langle 8\rangle ,\langle 9\rangle \}}
 
, the set of all three-digit decimal numbers is obtained as 
 
 
 
 D
 ⋅
 D
 ⋅
 D
 
 
 {\displaystyle D\cdot D\cdot D}
 
. The set of all decimal numbers of arbitrary length is an example for an infinite language.

<h2 id="alphabet-of-a-string">Alphabet of a string</h2>
The alphabet of a string is the set of all of the characters that occur in a particular string. If s is a string, its <a href="/facts/Alphabet_(computer_science)/6KW9qYRW">alphabet</a> is denoted by

Alph
        ⁡
        (
        s
        )
      
    
    {\displaystyle \operatorname {Alph} (s)}

The alphabet of a language 
 
 
 
 S
 
 
 {\displaystyle S}
 
 is the set of all characters that occur in any string of 
 
 
 
 S
 
 
 {\displaystyle S}
 
, formally:

Alph
 ⁡
 (
 S
 )
 =
 
 ⋃
 
 s
 ∈
 S
 
 
 Alph
 ⁡
 (
 s
 )
 
 
 {\displaystyle \operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s)}
 
.
For example, the set 
 
 
 
 {
 ⟨
 a
 ⟩
 ,
 ⟨
 c
 ⟩
 ,
 ⟨
 o
 ⟩
 }
 
 
 {\displaystyle \{\langle a\rangle ,\langle c\rangle ,\langle o\rangle \}}
 
 is the alphabet of the string 
 
 
 
 ⟨
 c
 a
 c
 a
 o
 ⟩
 
 
 {\displaystyle \langle cacao\rangle }
 
,
and the above 
 
 
 
 D
 
 
 {\displaystyle D}
 
 is the alphabet of the above language 
 
 
 
 D
 ⋅
 D
 ⋅
 D
 
 
 {\displaystyle D\cdot D\cdot D}
 
 as well as of the language of all decimal numbers.

<h2 id="string-substitution">String substitution</h2>
Let L be a <a href="/facts/Language_(computer_science)/crDTyP8q">language</a>, and let Σ be its alphabet. A string substitution or simply a substitution is a mapping f that maps characters in Σ to languages (possibly in a different alphabet). Thus, for example, given a character a ∈ Σ, one has f(a)=La where La ⊆ Δ<a href="/facts/Kleene_star/I6SX0f2Y">*</a> is some language whose alphabet is Δ. This mapping may be extended to strings as

f(ε)=ε
for the <a href="/facts/Empty_string/T7udJlmQ">empty string</a> ε, and

f(sa)=f(s)f(a)
for string s ∈ L and character a ∈ Σ. String substitutions may be extended to entire languages as <a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>

f
        (
        L
        )
        =
        
          ⋃
          
            s
            ∈
            L
          
        
        f
        (
        s
        )
      
    
    {\displaystyle f(L)=\bigcup _{s\in L}f(s)}

<a href="/facts/Regular_language/ahxw67T1">Regular languages</a> 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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
Similarly, <a href="/facts/Context-free_language/sHDxB5So">context-free languages</a> are closed under string substitution.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
A simple example is the conversion fuc(.) to uppercase, which may be defined e.g. as follows:

<table><tbody><tr><th>character</th><th>mapped to language</th><th>remark</th></tr><tr><th>x</th><th>fuc(x)</th><th></th></tr><tr><td>‹a›</td><td>{ ‹A› }</td><td>map lowercase char to corresponding uppercase char</td></tr><tr><td>‹A›</td><td>{ ‹A› }</td><td>map uppercase char to itself</td></tr><tr><td>‹ß›</td><td>{ ‹SS› }</td><td>no uppercase char available, map to two-char string</td></tr><tr><td>‹0›</td><td>{ ε }</td><td>map digit to empty string</td></tr><tr><td>‹!›</td><td>{ }</td><td>forbid punctuation, map to empty language</td></tr><tr><td>...</td><td></td><td>similar for other chars</td></tr></tbody></table>
For the extension of fuc to strings, we have e.g.

<ul><li>fuc(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},</li>
<li>fuc(‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, and</li>
<li>fuc(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.</li></ul>
For the extension of fuc to languages, we have e.g.

<ul><li>fuc({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹STRASSE› } ∪ { ‹U› } ∪ { } = { ‹STRASSE›, ‹U› }.</li></ul>
<h2 id="string-homomorphism">String homomorphism</h2>
A string homomorphism (often referred to simply as a <a href="/facts/Homomorphism/0gyqdEse">homomorphism</a> in <a href="/facts/Formal_language_theory/crDTyP8q">formal language theory</a>) is a string substitution such that each character is replaced by a single string. That is, 
 
 
 
 f
 (
 a
 )
 =
 s
 
 
 {\displaystyle f(a)=s}
 
, where 
 
 
 
 s
 
 
 {\displaystyle s}
 
 is a string, for each character 
 
 
 
 a
 
 
 {\displaystyle a}
 
.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
String homomorphisms are <a href="/facts/Monoid_morphism/6AHve7p8">monoid morphisms</a> on the <a href="/facts/Free_monoid/h3nPVjqr">free monoid</a>, preserving the empty string and the <a href="/facts/Binary_operation/CYtow0bz">binary operation</a> of <a href="/facts/String_concatenation/1npYg6rc">string concatenation</a>. Given a language 
 
 
 
 L
 
 
 {\displaystyle L}
 
, the set 
 
 
 
 f
 (
 L
 )
 
 
 {\displaystyle f(L)}
 
 is called the homomorphic image of 
 
 
 
 L
 
 
 {\displaystyle L}
 
. The inverse homomorphic image of a string 
 
 
 
 s
 
 
 {\displaystyle s}
 
 is defined as

 
 
 
 
 f
 
 −
 1
 
 
 (
 s
 )
 =
 {
 w
 ∣
 f
 (
 w
 )
 =
 s
 }
 
 
 {\displaystyle f^{-1}(s)=\{w\mid f(w)=s\}}

while the inverse homomorphic image of a language 
 
 
 
 L
 
 
 {\displaystyle L}
 
 is defined as

 
 
 
 
 f
 
 −
 1
 
 
 (
 L
 )
 =
 {
 s
 ∣
 f
 (
 s
 )
 ∈
 L
 }
 
 
 {\displaystyle f^{-1}(L)=\{s\mid f(s)\in L\}}

In general, 
 
 
 
 f
 (
 
 f
 
 −
 1
 
 
 (
 L
 )
 )
 ≠
 L
 
 
 {\displaystyle f(f^{-1}(L))\neq L}
 
, while one does have

 
 
 
 f
 (
 
 f
 
 −
 1
 
 
 (
 L
 )
 )
 ⊆
 L
 
 
 {\displaystyle f(f^{-1}(L))\subseteq L}

and

 
 
 
 L
 ⊆
 
 f
 
 −
 1
 
 
 (
 f
 (
 L
 )
 )
 
 
 {\displaystyle L\subseteq f^{-1}(f(L))}

for any language 
 
 
 
 L
 
 
 {\displaystyle L}
 
.
The class of regular languages is closed under homomorphisms and inverse homomorphisms.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> 
Similarly, the context-free languages are closed under homomorphisms<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> and inverse homomorphisms.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
A string homomorphism is said to be ε-free (or e-free) if 
 
 
 
 f
 (
 a
 )
 ≠
 ε
 
 
 {\displaystyle f(a)\neq \varepsilon }
 
 for all a in the alphabet 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
. Simple single-letter <a href="/facts/Substitution_cipher/PCTy2EJL">substitution ciphers</a> are examples of (ε-free) string homomorphisms.
An example string homomorphism guc can also be obtained by defining similar to the above substitution: guc(‹a›) = ‹A›, ..., guc(‹0›) = ε, but letting guc be undefined on punctuation chars. 
Examples for inverse homomorphic images are

<ul><li>guc−1({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, since guc(‹sss›) = guc(‹sß›) = guc(‹ßs›) = ‹SSS›, and</li>
<li>guc−1({ ‹A›, ‹bb› }) = { ‹a› }, since guc(‹a›) = ‹A›, while ‹bb› cannot be reached by guc.</li></ul>
For the latter language, guc(guc−1({ ‹A›, ‹bb› })) = guc({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }.
The homomorphism guc is not ε-free, since it maps e.g. ‹0› to ε.
A very simple string homomorphism example that maps each character to just a character is the conversion of an <a href="/facts/EBCDIC/qAhmvgj0">EBCDIC</a>-encoded string to <a href="/facts/ASCII/vGUI33Qu">ASCII</a>.

<h2 id="string-projection">String projection</h2>
If s is a string, and 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
 is an alphabet, the string projection of s is the string that results by removing all characters that are not in 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
. It is written as 
 
 
 
 
 π
 
 Σ
 
 
 (
 s
 )
 
 
 
 {\displaystyle \pi _{\Sigma }(s)\,}
 
. It is formally defined by removal of characters from the right hand side:

π
          
            Σ
          
        
        (
        s
        )
        =
        
          
            {
            
              
                
                  ε
                
                
                  
                    
                      if 
                    
                  
                  s
                  =
                  ε
                  
                    
                       the empty string
                    
                  
                
              
              
                
                  
                    π
                    
                      Σ
                    
                  
                  (
                  t
                  )
                
                
                  
                    
                      if 
                    
                  
                  s
                  =
                  t
                  a
                  
                    
                       and 
                    
                  
                  a
                  ∉
                  Σ
                
              
              
                
                  
                    π
                    
                      Σ
                    
                  
                  (
                  t
                  )
                  a
                
                
                  
                    
                      if 
                    
                  
                  s
                  =
                  t
                  a
                  
                    
                       and 
                    
                  
                  a
                  ∈
                  Σ
                
              
            
            
          
        
      
    
    {\displaystyle \pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{if }}s=\varepsilon {\mbox{ the empty string}}\\\pi _{\Sigma }(t)&{\mbox{if }}s=ta{\mbox{ and }}a\notin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s=ta{\mbox{ and }}a\in \Sigma \end{cases}}}

Here 
 
 
 
 ε
 
 
 {\displaystyle \varepsilon }
 
 denotes the <a href="/facts/Empty_string/T7udJlmQ">empty string</a>. The projection of a string is essentially the same as a <a href="/facts/Projection_in_relational_algebra/YgQm2wgA">projection in relational algebra</a>.
String projection may be promoted to the projection of a language. Given a <a href="/facts/Formal_language/crDTyP8q">formal language</a> L, its projection is given by

π
          
            Σ
          
        
        (
        L
        )
        =
        {
        
          π
          
            Σ
          
        
        (
        s
        )
         
        |
         
        s
        ∈
        L
        }
      
    
    {\displaystyle \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\}}

<h2 id="right-and-left-quotient">Right and left quotient</h2>
The right quotient of a character a from a string s is the truncation of the character a in the string s, from the right hand side. It is denoted as 
 
 
 
 s
 
 /
 
 a
 
 
 {\displaystyle s/a}
 
. If the string does not have a on the right hand side, the result is the empty string. Thus:

(
        s
        a
        )
        
          /
        
        b
        =
        
          
            {
            
              
                
                  s
                
                
                  
                    
                      if 
                    
                  
                  a
                  =
                  b
                
              
              
                
                  ε
                
                
                  
                    
                      if 
                    
                  
                  a
                  ≠
                  b
                
              
            
            
          
        
      
    
    {\displaystyle (sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}}

The quotient of the empty string may be taken:

ε
        
          /
        
        a
        =
        ε
      
    
    {\displaystyle \varepsilon /a=\varepsilon }

Similarly, given a subset 
 
 
 
 S
 ⊂
 M
 
 
 {\displaystyle S\subset M}
 
 of a monoid 
 
 
 
 M
 
 
 {\displaystyle M}
 
, one may define the quotient subset as

S
        
          /
        
        a
        =
        {
        s
        ∈
        M
         
        |
         
        s
        a
        ∈
        S
        }
      
    
    {\displaystyle S/a=\{s\in M\ \vert \ sa\in S\}}

Left quotients may be defined similarly, with operations taking place on the left of a string.
Hopcroft and Ullman (1979) define the quotient L1/L2 of the languages L1 and L2 over the same alphabet as L1/L2 = { s | ∃t∈L2. st∈L1 }.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
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 yielding {}, rather than { ε }.
The left quotient (when defined similar to Hopcroft and Ullman 1979) of a singleton language L1 and an arbitrary language L2 is known as <a href="/facts/Brzozowski_derivative/ceustUPV">Brzozowski derivative</a>; if L2 is represented by a <a href="/facts/Regular_expression/KFL3veHX">regular expression</a>, so can be the left quotient.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

<h2 id="syntactic-relation">Syntactic relation</h2>
The right quotient of a subset 
 
 
 
 S
 ⊂
 M
 
 
 {\displaystyle S\subset M}
 
 of a monoid 
 
 
 
 M
 
 
 {\displaystyle M}
 
 defines an <a href="/facts/Equivalence_relation/1MQ5rtkW">equivalence relation</a>, called the right <a href="/facts/Syntactic_relation/7khpKalF">syntactic relation</a> of S. It is given by

∼
          
            S
          
        
        
        
        =
        
        {
        (
        s
        ,
        t
        )
        ∈
        M
        ×
        M
         
        |
         
        S
        
          /
        
        s
        =
        S
        
          /
        
        t
        }
      
    
    {\displaystyle \sim _{S}\;\,=\,\{(s,t)\in M\times M\ \vert \ S/s=S/t\}}

The relation is clearly of finite index (has a finite number of equivalence classes) if and only if the family right quotients is finite; that is, if

{
        S
        
          /
        
        m
         
        |
         
        m
        ∈
        M
        }
      
    
    {\displaystyle \{S/m\ \vert \ m\in M\}}

is finite. In the case that M is the monoid of words over some alphabet, S is then a <a href="/facts/Regular_language/ahxw67T1">regular language</a>, that is, a language that can be recognized by a <a href="/facts/Finite-state_automaton/GMusWd0a">finite-state automaton</a>. This is discussed in greater detail in the article on <a href="/facts/Syntactic_monoid/7khpKalF">syntactic monoids</a>.

<h2 id="right-cancellation">Right cancellation</h2>
The right cancellation of a character a from a string s is the removal of the first occurrence of the character a in the string s, starting from the right hand side. It is denoted as 
 
 
 
 s
 ÷
 a
 
 
 {\displaystyle s\div a}
 
 and is recursively defined as

(
        s
        a
        )
        ÷
        b
        =
        
          
            {
            
              
                
                  s
                
                
                  
                    
                      if 
                    
                  
                  a
                  =
                  b
                
              
              
                
                  (
                  s
                  ÷
                  b
                  )
                  a
                
                
                  
                    
                      if 
                    
                  
                  a
                  ≠
                  b
                
              
            
            
          
        
      
    
    {\displaystyle (sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}}

The empty string is always cancellable:

ε
        ÷
        a
        =
        ε
      
    
    {\displaystyle \varepsilon \div a=\varepsilon }

Clearly, right cancellation and projection <a href="/facts/Commutative_property/WaYxJLxd">commute</a>:

π
          
            Σ
          
        
        (
        s
        )
        ÷
        a
        =
        
          π
          
            Σ
          
        
        (
        s
        ÷
        a
        )
      
    
    {\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)}

<h2 id="prefixes">Prefixes</h2>
The prefixes of a string is the set of all <a href="/facts/Prefix_(computer_science)/dM5Rqg6X">prefixes</a> to a string, with respect to a given language:

Pref
          
            L
          
        
        ⁡
        (
        s
        )
        =
        {
        t
         
        |
         
        s
        =
        t
        u
        
          
             for 
          
        
        t
        ,
        u
        ∈
        Alph
        ⁡
        (
        L
        
          )
          
            ∗
          
        
        }
      
    
    {\displaystyle \operatorname {Pref} _{L}(s)=\{t\ \vert \ s=tu{\mbox{ for }}t,u\in \operatorname {Alph} (L)^{*}\}}

where 
 
 
 
 s
 ∈
 L
 
 
 {\displaystyle s\in L}
 
.
The prefix closure of a language is

Pref
        ⁡
        (
        L
        )
        =
        
          ⋃
          
            s
            ∈
            L
          
        
        
          Pref
          
            L
          
        
        ⁡
        (
        s
        )
        =
        
          {
          
            t
             
            |
             
            s
            =
            t
            u
            ;
            s
            ∈
            L
            ;
            t
            ,
            u
            ∈
            Alph
            ⁡
            (
            L
            
              )
              
                ∗
              
            
          
          }
        
      
    
    {\displaystyle \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\}}

Example:

L
        =
        
          {
          
            a
            b
            c
          
          }
        
        
          
             then 
          
        
        Pref
        ⁡
        (
        L
        )
        =
        
          {
          
            ε
            ,
            a
            ,
            a
            b
            ,
            a
            b
            c
          
          }
        
      
    
    {\displaystyle L=\left\{abc\right\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}}

A language is called prefix closed if 
 
 
 
 Pref
 ⁡
 (
 L
 )
 =
 L
 
 
 {\displaystyle \operatorname {Pref} (L)=L}
 
.
The prefix closure operator is <a href="/facts/Idempotent/khbSpexv">idempotent</a>:

Pref
        ⁡
        (
        Pref
        ⁡
        (
        L
        )
        )
        =
        Pref
        ⁡
        (
        L
        )
      
    
    {\displaystyle \operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)}

The prefix relation is a <a href="/facts/Binary_relation/r9BwGgaK">binary relation</a> 
 
 
 
 ⊑
 
 
 {\displaystyle \sqsubseteq }
 
 such that 
 
 
 
 s
 ⊑
 t
 
 
 {\displaystyle s\sqsubseteq t}
 
 if and only if 
 
 
 
 s
 ∈
 
 Pref
 
 L
 
 
 ⁡
 (
 t
 )
 
 
 {\displaystyle s\in \operatorname {Pref} _{L}(t)}
 
. This relation is a particular example of a <a href="/facts/Prefix_order/l2R1yUTd">prefix order</a>.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Comparison_of_programming_languages_(string_functions)/ALwbntgo">Comparison of programming languages (string functions)</a></li>
<li><a href="/facts/Levi%2527s_lemma/CyYfXPwA">Levi's lemma</a></li>
<li><a href="/facts/String_(computer_science)/4ChJu5WS">String (computer science)</a> — definition and implementation of more basic operations on strings</li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Hopcroft, John E.; Ullman, Jeffrey D. (1979). <a href="https://archive.org/details/introductiontoau00hopc">Introduction to Automata Theory, Languages and Computation</a>. Reading, Massachusetts: Addison-Wesley Publishing. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-201-02988-8. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0426.68001">0426.68001</a>. (See chapter 3.)</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Hopcroft, Ullman (1979), Sect.3.2, p.60 <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.4, p.60 <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.2, p.131 <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">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. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Strictly formally, a homomorphism yields a language consisting of just one string, i.e. 
 
 
 
 f
 (
 a
 )
 =
 {
 s
 }
 
 
 {\displaystyle f(a)=\{s\}}
 
. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Hopcroft, Ullman (1979), Sect.3.2, p.60-61 <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.5, p.61 <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">This follows from the above-mentioned closure under arbitrary substitutions. <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.3, p.132 <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Hopcroft, Ullman (1979), Sect.3.2, p.62 <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Janusz A. Brzozowski (1964). "Derivatives of Regular Expressions". J ACM. 11 (4): 481–494. doi:10.1145/321239.321249. S2CID 14126942. <a href="/wiki/Janusz_Brzozowski_(computer_scientist)" target="_blank">/wiki/Janusz_Brzozowski_(computer_scientist)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
</ol>

String operations open-in-new

String operations