A string is a finite sequence of symbols from an alphabet.

A set of binary.

\Sigma\;=\;\{0,1\}

The notation above means strings of combinations of 0 and 1. Example:

\{0, 1, 01, 101, 00001, 100001, 0100, 1010, 10,\}

A set of English alphabet.

\Sigma\;=\;\{a, b, c,.....,x,y,z\}

Strings:

\{ab,cat,bed,cry,abc,def\}

No limit, sets of strings from the provided set.

A language is a set of strings:

L\;=\;\{0,10,100,1000,10000\}

The set above is a set of strings ending in 0.

A language can have meaning or nothing at all.

**Example: **

L\;=\;\{w|w\;ends\;in\;0\}

## Length of a string

The length of a string `w`

is written as `|w|`

, and is the number of symbols in that string.

**Examples: **

|010001110|\;=\;9\\|11|\;=\;2

The **empty string** is written as:

\epsilon\;or\;\lambda

\epsilon or \lambda in LaTex

**Examples:**

|\epsilon|\;=\;0\\|\epsilon10|\;=\;2\;=\;|10|

Formally, as string `w=w`

where each _{1}, w_{2}, ....., w_{n}`w`

is a symbol in an alphabet ∑._{i}

\Sigma\;=\;\{1,0\}

w\;=\;\{1,1,0\}\\w\;\;=\;\{w_1,w_2,w_3\}

## The Reverse String

The reverse string, `w`

is written:^{R}

w^R\;=\;\{w_n,...,w_2,w_1\}

So the example above for {1,1,0}:

w^R\;=\;\{0,1,1\}

Written in reverse…

More examples:

011011^R\;=\;110110

Sometimes a string is equivalent to its reversed. It’s called – **palindrome**.

Palindrome – A palindrome is a word, sentence, verse, or even number that reads the same backward or forward. It derives from Greek roots that literally mean “running back” (palin is “again, back,” and dromos, “running.”) The word appears to have been created in English based on these roots in the early 1600s.

**Example:**

101^R\;=\;101

## Substring

A string `z`

is a substring of `w`

iff(if and only if) `z`

appears exactly in w.

**Examples: **

\epsilon\;or\;\lambda\;is\;always\;a\;substring\;of\;a\;larger\;string

## Concatenation

Taking two strings and joining them together.

If we have two strings `x`

and `y`

such that:

x\;=\;x_1,x_2,.....,x_n\\y\;=\;y_1,y_2,.....,y_m

then the concatenation of `x`

and `y`

is:

w\;=\;xy\;=\;x_1,x_2,.....,x_n,y_1,y_2,.....,y_m

For example:

x\;=\;01\;and\;y\;=\;110\\xy\;=\;01110\\yx\;=\;11001

if\;x\;=\;0100\;and\;y\;=\;110\;then:\\xy\;=\;0100110\\y^2x\;=\;yyx\;=\;1101100100

## Exercise:

\Sigma\;=\;\{a,b\},x\;=\;abab,y\;=bbbb,z\;=\;ab

1 – Find the length of x, y, and z.

|x|\;=\;|abab|\;=4\\|y|\;=\;|bbbb|\;=\;4\\|z|\;=\;|ab|\;=2

2 – What is xyyz?

xyyz\;=\;ababbbbbbbbbab

3 – Find x^{R}.

x^R\;=\;baba

4 – Is z a substring of x? Yes

5 – Is z^{R} a substring of x^{R}? Yes