Select this to skip to main content [CSUSB] >> [CNS] >> [Comp Sci ] >> [R J Botting] >> [MATHS] >> intro_strings
 [Index] || [Contents] || [Source] || [Definitions] || [Search] || [Notation] || [Copyright] || [Comment] Fri Jan 16 12:32:02 PST 2004

Contents


    Strings and n-tpls

    There are several models of strings. Suppose we have a set of symbols(T say) then the strings are generated by starting with an empty string ("") and a putting symbols (in T) onto it using a concatenation operation (!).

  1. concatenation::function=`combines to strings into one by juxtaposing them".
  2. !::infix= concatenation. Example:
  3. (def) |- "abc" ! "xyz" = "abcxyz", Some axioms:
  4. |- (empty): for x:strings, "" ! x = x ! "" =x.
  5. |- (associativity): For x,y,z:strings, x !(y!z)=(x!y)!z. And so on... [ math_62_Strings.html ] [ math_61_String_Theories.html ] [ logic_6_Numbers..Strings.html ]

    We can also, if we want, treat a strings as n_tples of characters and define concatenation in terms of this model.

    We define operations of union(|), intersection (&), complementation (~), concatenation(), and iteration (#) on sets of strings:

    For A,B: sets of strings,

  6. A B::={c || c=a!b and a in A and b in B},
  7. #A::=least{ X || X=({""} | A X) }.

  8. For string s, s::={s} (in context demanding a set of strings, only)

    Given a string s with n symbols in it then

  9. |-|s|=n,
  10. |-head(s)=s(1)=the first symbol in s,
  11. |-tail(s)=all sybols except the first in s,
  12. |-if|s|>=1 then s=head(s)!tail(s) ,


  13. |-last(s)=s(|s|).

    Functions mapping strings into strings

    These are neatly defined in terms of the set of functions

  14. { (head), (tail), (!), (last), ...} using XBNF. For example

  15. reverse("")::="",
  16. reverse::string~"" -> string=reverse(tail) ! (head).

    n_tples

    Given a set of objects S then %S is the set of functions

  17. 1..n->S for some n:0,1,2,3,... The concatentaion operation is defined on them.


  18. |-%(%S)=two dimensional arrays of S's
  19. |-#(%S)=%(S).
  20. |-%(%S)<>%(S).

    LISTS


  21. |-lists(S)=S| %S | %%S | %%%S | .... In other words the set of objects defined as containing S and all n-tuples of objects in S or lists(S).

    LISP

    In LISP every thing is defined in terms of
  22. |- PAIR::=Net{ car,cdr:List } where
  23. |- List::= Atom | NIL | $ PAIR.


Formulae and Definitions in Alphabetical Order