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