## Basic knowledge of String in Theory of Compuation

Symbol:

A symbol is user define entity which is any single object.

Example:1, 0, a, #, & etc.

String Alphabet:

An alphabet is a finite set of symbols denoted by ∑ in theory of computation. An alphabet is a set of symbols like ∑ = {a, b} or ∑ = {0, 1} or ∑ = {a, b, #, &} etc. which is used to construct a set of strings that represent a language.

String:

A string is defined as a sequence of symbols of finite length. A string is denoted by ω in the Theory of Computation.

As an example ω = 0001100 (binary string), ω = aaabba (alphabet string) or empty string = λ.

# Length of string:

Number of symbols in string ω. As an example ω = aabbaab so, length of | ω | = 7.

# Concatenation:

Example:

# Prefix:

A prefix of a string is the string formed by taking any number of symbols that are added to the beginning of a string.

Example:

Let us take a string ω = 01011. Now the prefixes are {λ, 0, 01, 010, 0101, 01011}. Here string length of | ω | = 5 and number of prefix is 6

In general, if the length of the string is n, there are n + 1 number prefixes that are possible.

Proper prefix means any prefix of the string other than the string itself.

Like for above example

There are {λ, 0, 01, 010, 010} proper prefixes.

In general, if the length of the string is n, there are n number proper prefixes are possible.

# Suffix:

A suffix of a string formed by taking any number of symbols from the end of the string.

Example:

Let us take a string ω = 01011. Now the suffixes are {λ, 1, 11, 011, 1011, 01011}. Here string length of | ω | = 5 and the number of the prefix is 6

In general, if the length of the string is n, there are n + 1 number suffixes that are possible.

Proper suffix means any suffix of the string other than the string itself. Like for above example

There are {λ, 1, 11, 011, 1011} proper suffixes.

In general, if the length of the string is n, there are n number proper suffixes are possible.

Note: The number of prefixes and suffixes are the same but symbols in the prefix and suffix set are not the same.

ω = 01011

Prefixes = {λ, 0, 01, 010, 0101, 01011}

Suffixes = {λ, 1, 11, 011, 1011, 01011}

Substring:

A substring of a string is a string formed by taking a contiguous sequence of symbols within a string.

Let, ω = aba

a b a,   λaba,    λ,   λaba     Substring = {b, aba, a, ba, ab, λ}

Power of strings:

Reverse:

Note:

See next topic:

Power of Alphabet (∑)

Related