Definition : A sequence is list in which order is taken into account.
We can consider a sequence { x_i | i ³ 0}as a function y : Z ® X where Z is the set of non-negative integers.

A sequence s is increasing if s _n £ s _n+1 for all n .

A sequence s is decreasing if s _n ³ s _n+1 for all n .

Definition : Subsequence

Given a sequence X = { x₁,x₂,….. } and another sequence Z = {z₁,z₂,……. }is a subsequence of X if there exists a strictly increasing sequence { i<1> , i<2>, ….. } of indices of X such that for all j = 1,2,3 …, we have x _i<j> = z_j .

 

Definition : A string over X is a finite sequence of elements from X .

The string with no elements is called the null string and is denoted l (sometimes e ).

X* denotes the set of all strings over X and X⁺ denotes the set of all non-null stings over X.

The length of a string a is the number of elements in a .

If a and b are two strings , the string consisting of a followed by b , written as a b , is called the concatenation of a and b .