##### Empty String | Theory of Computation
 Empty string

• Definition -The empty string is the string with zero occurrence of symbols. This string is represented as є or λ.
• Example -

The set of strings, including the empty string, over an alphabet ∑ is denoted by ∑*.
For ∑ = {0, 1} we have set of strings as ∑* = {є, 0, 1, 01, 10, 00, 11, 10101,…}. and ∑1 = {0, 1} , ∑2 = {00, 01, 10, 11} and so on.

∑* contains an empty string є. The set of non- empty string is denoted by ∑+.

#### Contributor's Info

Created:
##### Basic operations of Strings | | Theory of Computation
 Operations on Strings

1) Length of a String :

• Definition − It is the number of symbols present in a string. (Denoted by |S|).
• Examples −
• If S = ‘cabcad’, |S|= 6
• If |S|= 0, it is called an empty string (Denoted by λ or ε)

2)Substring:

• Definition – A sequence of symbols from any part of the given string over an alphabet is called a “substring of a string”.
• Examples −

For string abb over ∑={a,b}. The passive substrings are:

• Zero length substring: ε
• One  length substring: a,b
• Two  length substring: ab,aa
• Three  length substring: aab, baa

3)Concatenation:

• Definition - combines two strings by putting them one after the other.
• Example -

x = abc, y = mnop, then x ◦ y = abcmnop, or simply xy = abcmnop

The concatenation of the empty string with any other string gives the string itself: x e = ex = x

4)Reversal :

• Definition - Reversal of a string w denoted w R is the string spelled backwards

Formal definition:

• If w is a string of length 0, then w R= w = e
• If w is a string of length n+1 > 0, then w = ua for some a є∑, and w R= a u R.

5)Prefix of a string:

• Definition - A substring with the sequence of beginning symbols of a given string is called a “prefix”.
• Example -

For a string abb , the possible prefixes of abb are:

• ε (zero length prefix)
• a(one length prefix)
• ab (two length prefix)
• abb (three length prefix)

6)Suffix of a string:

• Definition - A substring with the sequence of ending symbols of a given string is called a “suffix”.
• Example -

For a string abb , the possible suffixs of abb are:

• ε (zero length suffix)
• b(one length suffix)
• ba (two length suffix)
• bba (three length suffix)

7)Proper prefix of a string:

• Definition -Proper prefix is a prefixes except the given string.
• Example -

For a string abb, the possible proper prefixes are : ε, a , ab.

8)Proper suffix of a string:

• Definition -Proper suffix is a suffix except the given string.
• Example -

For a string abb, the possible proper suffix  are : ε, b , ba.

Created: