FORMAL LANGUAGES AND

AUTOMATA THEORY

II B.Tech - II Sem ( R19)

1
 UNIT – I: Finite Automata
Why Study Automata Theory? The Central
Concepts of Automata Theory.

2
What is Automata Theory?
 Study of abstract computing devices, or
“machines”.
 Automaton = an abstract computing device
 Note: A “device” need not even be a physical hardware!

3
(A pioneer of automata theory)

Alan Turing (1912-1954)

 Father of Modern Computer
Science
 English mathematician
 Studied abstract machines called
Turing machines even before
computers existed

4
Theory of Computation:
A Historical Perspective
1930s • Alan Turing studies Turing machines
• Decidability
• Halting problem
1940-1950s • “Finite automata” machines studied
• Noam Chomsky proposes the
“Chomsky Hierarchy” for formal
languages
1969 Cook introduces “intractable” problems
or “NP-Hard” problems
1970- Modern computer science: compilers,
computational & complexity theory evolve
5
Noam Chomsky Classification of grammars

6
The Concepts of
Automata Theory

7
Alphabet
An alphabet is a finite, non-empty set of symbols.
∑ (sigma) is used to denote an alphabet.

 Examples:
 Binary : ∑ = {0,1}
 All lower case letters : ∑ = {a,b,c,..z}
 Alphanumeric : ∑ = {a-z, A-Z, 0-9}
 DNA molecule letters : ∑ = {a,c,g,t}
 … 8
Strings
A string or word is a finite sequence of symbols
chosen from ∑. A string can be represented by
any letter.
 Length of a string w, denoted by “|w|”, is equal to
the number of (non- ) characters in the string
 E.g., x = 010100 |x| = 6
 x = 01  0  1  00  |x| = ?

 xy = concatentation of two strings x and y 9

String Operations:
I. Length of a string

II. Concatenation of a string

III. Prefix of a string
IV. Suffix of a string

V. Proper Prefix/ Suffix of a string

VI. Substrings of a string
VII. Proper Substring of a string

10
(i) Length of a String : It is the number of symbols present
in a string. If ‘w’ is a string then the length of a string is
denoted by |w|.

Ex:
If S=‘cabcad’, |S|= 6
If n=010 |n|=3

Empty string: A string , which is of length zero ( 0 ) is

called empty string and is denoted by λ or ε (or “epsilon”)

Ex:
If | ε |= 0, it is called an empty string

11
(ii) Concatenation of Strings

 If ‘ w1‘ and ‘ w2‘ are two strings then

concatenation of ‘ w1‘ and ‘ w2‘ is a string
demoted by ‘w1w2‘ . In other words, we can say
that ‘ w1‘ is followed by ‘ w2‘ .

 The length of concatenated string by ‘w1w2‘ is = | w1w2|

 If x = 010100 |x| = 6
y = 00 |y| = 2

 xy = 010100 00 is concatenation of two

strings x and y 12
 |xy| = 8
(iii) Prefix of a String : It is a string obtained by removing
zero ( 0 ) or more trailing symbols is called prefix of a string

Ex:
If a string w = abc
prefixes set of w {ϵ, a,ab,abc }

(iv) Suffix of a String : It is a string obtained by removing

zero ( 0 ) or more leading symbols is called suffix of a
string .
Ex:
If a string w = abc
Suffixes set of w {ϵ, c,bc,abc }

13
(v) Proper Prefix / Suffix of a String :
A string ‘a’ is said to be proper prefix / Suffix of string ‘w’ if
and only if a ǂ w .

Ex:

If a string w = abc

Proper Prefix of w {ϵ ,a, ab }

Proper Suffix of w {ϵ , c, bc }

14
(vi) Substring: A string obtained by removing proper prefix
or proper suffix of a string ‘w’ , is called substring of ‘w’.

Substring of w = w – ( one of the proper prefix/sufix )

Ex:
If a string w = abc
Substrings of w {ϵ ,a,b,ab,bc,abc }

Note:
ϵ is a substring of every string.

15
(vii) Proper Substring: A proper substring is any substring
s of string t where s ≠ t.

i.e A substring t is a proper substring of s iff s ≠ t.

Ex: That is, "hi" is a substring of "hi", but not a proper

substring.

If a string w = abc
Proper substrings of w {ϵ ,a,b,ab,bc }

Note:
ϵ is a substring, prefix, and suffix of every string.

16
 Empty Set: (Ø )
The set containing no elements, commonly
denoted  using Ø

Ø= { }

Note :
That ∅ ǂ {ε}, because the language ∅ does not contain any
string but {ε} contains a string, namely ε.

Also it is evident that |∅| = 0; whereas, |{ε}| = 1.

17
Powers of an alphabet

Let ∑ be an alphabet.

 ∑k = the set of all strings of length k

 ∑* = ∑0 U ∑1 U ∑2 U …

 ∑ + = ∑ 1 U ∑2 U ∑ 3 U …

 ∑0 = { ϵ } - Set of Empty String

 Note: ∑* - Is called Universal set

19
 Kleene Star (Σ* ):
 Definition : The set Σ* is the infinite set of all
possible strings of all possible lengths over Σ
including λ.
 Representation : Σ* = Σ0 ∪ Σ1 ∪ Σ2 ∪…….
 Example :

If Σ = {a, b},
Σ* = {λ, a, b, aa, ab, ba, bb,………..}

20
Kleene Plus ( Σ+ ):
 Definition : The set Σ+ is the infinite set of all possible
strings of all possible lengths over Σ excluding λ.

 Representation :
Σ* = Σ0 ∪ Σ1 ∪ Σ2 ∪…….

Σ+ = Σ* − { λ }
 Example :
If Σ = { a, b } ,

Σ+ = { a, b, aa, ab, ba, bb,………..}

21
22
 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, bb, ba, bb}

23
24