What is a formal language in automata theory?

Formal Language in Automata Theory

Automata Theory – Formal Language

In automata theory, a formal language is a set of strings of symbols drawn from a
finite alphabet.

A formal language can be specified either by a set of rules (such as regular expressions or a
context-free grammar) that generates the language, or by a formal machine that accepts (recognizes) the language.

A formal machine takes strings of symbols as input and outputs either “yes” or “no.”

Alternatively, a language can be defined as the set of strings for which a particular
machine says “yes.”

Formal languages can be grouped into a series of successively larger classes known as
the Chomsky hierarchy.

Symbols: Any single object is called symbol, for example:- 1,0, A , a , @ , # are

Alphabets: Alphabet is finite, non-empty set of symbols denoted by Σ.
Σ = { 0,1 } , Σ = {a,b,c} are examples of alphabet.

Strings or words over Σ: String is a finite sequence of symbols from some

Consider alphabet , Σ = { 0,1 } then w1= 010 , w2= 0111.

Length of the string: It is the number of symbols in the string.
The length of empty string is 0
i.e., |ε| = 0 ; |w| = | aaba| = 4. It does not matter if the alphabets are repeated.

Concatenation of strings: It is nothing but to join two shorter strings to make a
single larger string.
w3= 010 , w4= 0111 => w7= 0100111 is concatenation of w3 .w4 .
w1 w2= ε . b = b . ε = b , where w1= ε and w2= b

Kleene Closure: The Kleene closure, ∑* is a unary operator on a set of symbols or strings, ∑, that gives the infinite set of all possible strings of all possible lengths over ∑ including ε.

Example − If ∑ = {a, b}, ∑* = {λ, a, b, aa, ab, ba, bb,………..}

Kleene Plus: The set ∑+ is the infinite set of all possible strings of all possible lengths over ∑ excluding ε.
Example − If ∑ = { a, b } , ∑+ = { a, b, aa, ab, ba, bb,………..}

+ = ∑* − {ε}

Language: A language is a subset of ∑* for some alphabet ∑. It can be finite or
Example − If the language takes all possible strings of length 2 over ∑ = {a, b},
then L = { ab, aa, ba, bb }

Formal Language Example

Symbols: a, b, c, d, e

Alphabet: ∑ = {a, b, c}



Language: String of length less than 3 from ∑.

{ε,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc} -> Finite Set

|w7| = |ac| = 2

|w1| = |ε| = 0

Leave a Reply 0

Your email address will not be published. Required fields are marked *