 [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

# 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,

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.