Day 52 – Alphabets and Strings in Discrete Math

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=w1, w2, ....., wn where each wi is a symbol in an alphabet ∑.

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

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

The Reverse String

The reverse string, wR is written:

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

More Resources: