Automata Theory and Formal Languages

Alphabets and Language

A subset of string over an alphabet is a language.

An alphabet is a finite, non-empty set of symbols. Conventionally, the symbols Σ is used for an alphabet.

Common alphabet include :

  1. 1. Σ {0,1}, the binary alphabet.
  2. 2. Σ {A,B,…..,Z}, the set of uppercase letters.
  3. 3. Σ {0,1,2……,9}, the decimal alphabet.

A string is a finite sequence of symbols from the alphabets. For Example :

  • 10110 is a string from the binary alphabet.
  • 5920 is a string from the decimal alphabet.
  • STAMP‘ is a string from the roman alphabet.

A string having no symbol is known as an empty string. An empty string is denoted by ε.

The exponential notation is used to express the set of all strings of a certain length.

        Σk = set of strings of length k, each of whose symbol is in Σ.

For example,

        if Σ = {0,1}
        then Σ1 = {0,1}
         Σ2 = {00,01,10,11}
         Σ0 = {ε}

The reversal of string ω is denoted by ωR.

For example,

        if ω = xyz
         then ωR = zyx.

A string v is a substring of a string ω if and only if there are strings x and y such that,

        ω = x v y, where both x and y could be null

Every string is a substring of itself.

For emample,

        if ω = ‘abcdef’ is a string.

then ‘cef’ is a substring ω.

For each string ω, the string ωi is defined as,

        ω0 = ε, the empty string

        ωi+1 = ωi . ω for each i ≥ 0 where i is a natural number.

For example,

        if ω = abb
        then ω0 = ε
        ω1= abb
        ω2= ω. ω = abbabb
        ω3= ω2. ω = abbabbabb

The set of all strings over an alphabet Σ is denoted by Σ*.

                Σ* = Σ0 ∪ Σ1 ∪ Σ2……….

For example,

        if Σ = {0,1}
        then Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001,…….}

A subset of string over an alphabet Σ is a language. In other words, any subset of Σ* is a language.

For example,

        if L1 = [ω Ε {0,1}* | ω has a equal number of 0’s and 1’s ]

    i.e., L1 = is a language over alphabets {0,1}, having equal of 0’s and 1’s .

Above rule say that create string which should contain number of 0’s and 1’s equals.

   ∴     if L1 = {ε, 01, 10, 1100, 0101, 1100, 1010, ,……..}

        Thus, a language can be specified by:

                if L1 = {ω Ε Σ* | ω has given property ]

Some example of language are:

  1. 1. A language of all strings, where the string represents is a binary number.
  2. {0, 1, 00, 01, 10, 11 ………}
  3. 2. The set of a string of 0’s and 1’s with an equal number of each.
  4. {ε, 01, 011, 0101, 1010, 1100,…….}
  5. 3. The set of a string of 0’s and 1’s ending in 11.
  6. {11, 011, 111, 0011, 0111, 1011,………}
  7. 4. Σ* is a language for any alphabets Σ.
  8. 5. Ф, the empty language, is a language over an alphabet.
  9. 6. {ε}, the language consisting of only the empty string, is also a language over any alphabet.

Recommended:

  1. Kleene Closure
  2. Recursive Definition of a Language
  3. Finite Representation of Language

Leave a Comment

Your email address will not be published. Required fields are marked *

x