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: Edited:
0Comment
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.

Contributor's Info

Created: Edited:
0Comment