Strings

A string is a sequence of elements from an alphabet.

An alphabet is a a collection of symbols.

An alphabet can be either finite or infinite.

An empty string, $\lambda$, has no characters, and therefore $\lambda$ does not contribute to the length of a string.

Equality

Two strings are equal if the have the same number of characters in the same order.

If a string has a empty string inside it, we essentially ignore the empty string.

$$\underbrace{\text{Hello}}_5=\underbrace{\text{Hel}\textcolor{red}\lambda \text{lo}}_5$$

Concatenation

Two strings $s,t$ can be concatenated to form $st$.

$$\text{spider + man = spiderman}$$

Prefixes

Given two strings $s,t$, we say that $s$ is a prefix of $\text{t}$ if $t=su$.

A string has $\lambda$ as a prefix, as well as itself.

$$\underbrace{\text{spiderman}}_t = \underbrace{\text{\textcolor{#f55}{spi}}}_s\underbrace{\text{derman}}_u\\ \underbrace{\text{spiderman}}_t = \underbrace{\textcolor{#f55}\lambda}_s\underbrace{\text{spiderman}}_u\\ \underbrace{\text{spiderman}}_t = \underbrace{\text{\textcolor{#f55}{spiderman}}}_s\underbrace{}_u$$

Suffixes

Given two strings $s,t$, we say that $s$ is a suffix of $t$ if $t=us$.

A string has $\lambda$ as a suffix, as well as itself.