# 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.