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
symbols.
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
alphabet.
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
infinite.
Example − If the language takes all possible strings of length 2 over ∑ = {a, b},
then L = { ab, aa, ba, bb }
Formal Language Example
#Automata Theory #Formal Language #Kleene Closure #Kleene PlusSymbols: a, b, c, d, e
Alphabet: ∑ = {a, b, c}
∑*={ε,a,b,c,ab,ba,bc,bb,bbb,aab,…}
∑+={a,b,c,ab,ba,bc,bb,bbb,aab,…}
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