String operations: Difference between revisions

Revision as of 12:58, 4 April 2018

Revision as of 15:46, 18 July 2018

Line 49:

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''_uc(.) to upper caseuppercase, which may be defined e.g. as follows:

{| class="wikitable"

Line 57:

! ''x'' !! ''f''_uc(''x'') !!

|-

| ‹''a''› || { ‹''A''› } || map lower-caselowercase char to corresponding upper-caseuppercase char

|-

| ‹''A''› || { ‹''A''› } || map upper-caseuppercase char to itself

|-

| ‹''ß''› || { ‹''SS''› } || no upper-caseuppercase char available, map to two-char string

|-

| ‹0› || { ε } || map digit to empty string