Basic Terminologies

1.  Alphabet

    An alphabet is a finite, non-empty set of symbols. The symbol ∑ is used for representing it.

Example: 

Binary language: Alphabet = {0, 1}

English language: Alphabet = {a, b, c, ...,z}

2. String

A string is a finite sequence of symbols chosen from some alphabet. 

Example:

101101 is a string that belongs to binary language.

2.1 Empty string

Empty string is a string with zero occurrences of symbols. It is denoted by the symbol ε. 

2.2 Length of the string

The length of the string is the number of characters occurring in any given string.

Example:

The length of the string 10110 is 5. We denote the length of the string s=10110 as |s|.

2.3 Powers of an alphabet

The power of an alphabet ∑ is represented as ∑ ^k where k represents length of the the set of strings.

Example:

∑ ⁰ = ε

∑ ¹ = {1, 0}

∑ ² = {01, 00, 11, 10}

Special cases:

Kleene closure (∑ ^* ) = ∑ ⁰ U ∑ ¹ U ∑ ² U ….

Positive Closure (∑ ⁺) = ∑ ¹ U ∑ ² U ….

3. Language

The set of strings chosen from ∑ ^*  is known as the language.

Example:

The binary language = {0, 01, 101, 11101, .....}