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 Σ¹ = {0,1}
         Σ² = {00,01,10,11}
         Σ⁰ = {ε}

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 ωⁱ is defined as,

        ω_⁰ = ε, the empty string

        ωⁱ⁺¹ = ωⁱ . ω for each i ≥ 0 where i is a natural number.

For example,

        if ω = abb
        then ω_⁰ = ε
        ω¹= abb
        ω_²= ω. ω = abbabb
        ω³= ω². ω = abbabbabb

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

                Σ^* = Σ⁰ ∪ Σ¹ ∪ Σ²……….

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