Strings

Alphabet - a finite set of symbols. A member of an alphabet is a "character" or "symbol".

• Example: A = {0,1} is the binary alphabet.
• Example: ASCII and EBCDIC are two programming alphabets.

String - a finite sequence of symbols.

• | $x$ | = the number of symbols in string $x$ (length of $x$)
• $\varepsilon$ = string of length 0 (null or empty string)
• Example: 001101 is a string of length 6

Concatenation of strings $x$ and y - the string formed by appending the symbols of $y$ to the symbols of $x$, written as $x$ $\cdot$ $y$ or $xy$.

• Example: Let $x$ = abc and $y$ = de (a,b,c,d,e are symbols; $x$,$y$ are strings).
  $x$ $\cdot$ $y$ = abcde
  $\varepsilon$ $\cdot$ $y$ = $y$ $\cdot$ $\varepsilon$ = $y$
  
• Let $x^i$ = $x$ $\cdots$ $x$ (i $x$'s concatenated) and $x^0$ = $\varepsilon$. Then $x^2$ = $x$ $\cdot$ $x$ = abcabc.

Note: Concatenation of strings is analogous to multiplication with $\varepsilon$ = 1, but is not commutative.