1. Definition
A Formal Language is a set of strings formed using symbols from a fixed set of symbols called an alphabet.
In simple words:
Formal Language = A collection of valid strings made from a given alphabet according to specific rules.
Formal languages are used in Theory of Computation, programming languages, compilers, and automata theory.
2. Alphabet
An alphabet is a finite, non-empty set of symbols.
It is generally represented by Σ (Sigma).
Example:\[ Σ = \{0,1\} \]
Here, 0 and 1 are symbols of the alphabet.
Another example:\[ Σ = \{a,b,c\} \]
3. String
A string is a finite sequence of symbols taken from an alphabet.
If:\[ Σ = \{0,1\} \]
Then examples of strings are:
01011010111001
The empty string is represented by ε (epsilon).
It contains zero symbols.\[ |\epsilon|=0 \]
4. Language
A language is a set of strings over an alphabet.
For example, if:\[ Σ=\{0,1\} \]
then:\[ L=\{0,1,01,10,101\} \]
is a language over Σ.
Another example:\[ L=\{0,00,000,0000,\ldots\} \]
This language contains strings consisting only of zeros.
5. Kleene Star
The Kleene star is represented by:\[ Σ^* \]
It represents all possible finite strings, including the empty string ε, that can be formed using symbols of Σ.
For:\[ Σ=\{a,b\} \]
we have:\[ Σ^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,\ldots\} \]
There are infinitely many strings.
6. Important Terms
| Term | Meaning |
|---|---|
| Alphabet (Σ) | Set of symbols |
| String | Sequence of symbols |
| ε | Empty string |
| Language (L) | Set of strings |
| Σ* | All possible finite strings including ε |
| Σ⁺ | All non-empty strings |
Relationship:\[ Σ^+ = Σ^*-\{\epsilon\} \]
7. Example
Suppose:\[ Σ=\{a,b\} \]
Consider the language:\[ L=\{w \mid w \text{ starts with }a\} \]
Some strings belonging to L are:
aabaaabaabb
But:
bbabb
do not belong to L.
Exam Answer — 5 Marks
Formal Language is a collection of strings formed from a finite set of symbols called an alphabet. An alphabet is represented by Σ. A finite sequence of symbols from an alphabet is called a string. The empty string is represented by ε. A language L is a set of strings over an alphabet Σ. The set of all possible strings including the empty string is represented by Σ*. Formal languages are important in automata theory, compiler design, programming languages and Theory of Computation.
Example:\[ Σ=\{0,1\} \]\[ L=\{0,01,10,101\} \]
Here, Σ is the alphabet and L is a formal language over Σ.
⭐ Remember this for exam
Alphabet → Symbols
String → Sequence of symbols
Language → Set of strings
Σ* → All possible strings
ε → Empty string
