CREATE OWN LIBRARY

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 (∑)