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.