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 (!).
- concatenation::function=`combines to strings into one by juxtaposing them".
- !::infix= concatenation.
Example:
- (def) |- "abc" ! "xyz" = "abcxyz",
Some axioms:
- |- (empty): for x:strings, "" ! x = x ! "" =x.
- |- (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,
- A B::={c || c=a!b and a in A and b in B},
- #A::=least{ X || X=({""} | A X) }.
- For string s, s::={s} (in context demanding a set of strings, only)
Given a string s with n symbols in it then
- |-|s|=n,
- |-head(s)=s(1)=the first symbol in s,
- |-tail(s)=all sybols except the first in s,
- |-if|s|>=1 then s=head(s)!tail(s) ,
- |-last(s)=s(|s|).
Functions mapping strings into strings
These are neatly defined in terms of the set of functions
- { (head), (tail), (!), (last), ...}
using XBNF. For example
- reverse("")::="",
- reverse::string~"" -> string=reverse(tail) ! (head).
n_tples
Given a set of objects S then %S is the set of functions
- 1..n->S for some n:0,1,2,3,...
The concatentaion operation is defined on them.
- |-%(%S)=two dimensional arrays of S's
- |-#(%S)=%(S).
- |-%(%S)<>%(S).
LISTS
- |-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
- |- PAIR::=Net{ car,cdr:List }
where
- |- List::= Atom | NIL | $ PAIR.
