Skip to content
Home » Formal Language

Formal Language

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:

  • 0
  • 1
  • 01
  • 10
  • 101
  • 11001

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

TermMeaning
Alphabet (Σ)Set of symbols
StringSequence 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:

  • a
  • ab
  • aa
  • aba
  • abb

But:

  • b
  • ba
  • bb

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