Module-1

Introduction to Automata
Theory

2/16/2023 Dakhole Dipali K

1
 Models of Computation

2/16/2023 Dakhole Dipali K 2

 Computation

CPU memory

2/16/2023 Dakhole Dipali K 3

 temporary memory

input memory
CPU
output memory

Program memory

2/16/2023 Dakhole Dipali K 4

 Example: f ( x) = x 3

temporary memory

input memory
CPU
output memory
Program memory
compute xx

2/16/2023
compute x x2
Dakhole Dipali K 5
 f ( x) = x 3

temporary memory
input memory
x=2
CPU
output memory
Program memory
compute xx

2/16/2023
compute x x2
Dakhole Dipali K 6
 temporary memory f ( x) = x 3
z = 2*2 = 4
f ( x) = z * 2 = 8
input memory
x=2
CPU
output memory
Program memory
compute xx

2/16/2023
compute x x2
Dakhole Dipali K 7
 temporary memory f ( x) = x 3
z = 2*2 = 4
f ( x) = z * 2 = 8
input memory
x=2
CPU
f ( x) = 8
Program memory output memory
compute xx

2/16/2023
compute x x2
Dakhole Dipali K 8
 Automata theory is the study of
abstract machines and automata.
The computational problems can be
solved using them.
It is a theory in theoretical computer
science and discrete mathematics

2/16/2023 Dakhole Dipali K 9

 Automaton
temporary memory

Automaton
input memory
CPU
output memory

Program memory

2/16/2023 Dakhole Dipali K 10

 Different Kinds of Automata
Automata are distinguished by the temporary memory

• Finite Automata: no temporary memory

• Pushdown Automata: stack

• Turing Machines: random access memory

2/16/2023 Dakhole Dipali K 11

 Finite Automaton

temporary memory

Finite input memory

Automaton
output memory

Example: Vending Machines (small computing power)

2/16/2023 Dakhole Dipali K 12

 Pushdown Automaton
Stack Push, Pop

Pushdown input memory

Automaton output memory

Example: Compilers for Programming Languages

(medium computing power)

2/16/2023 Dakhole Dipali K 13

 Turing Machine

Random Access Memory

input memory
Turing
Machine output memory

Examples: Any Algorithm (highest computing power)

2/16/2023 Dakhole Dipali K 14

 Power of Automata

Finite Pushdown Turing

Automata Automata Machine
Less power Solve more More power
computational problems

2/16/2023 Dakhole Dipali K 15

Applications of finite automata

➢ For the designing of lexical analysis of a compiler which breaks the

input text into logical units like identifiers, keywords etc.
➢ For recognizing the pattern using regular expressions.
➢ For the designing of the combination and sequential circuits.
➢ Software for designing and checking the behavior of digital circuits.
➢ Used in text editors.
➢ For the implementation of spell checkers.
➢ Software for scanning large bodies of text like web pages to find
occurrence of words, phrases and other patterns.
➢ Software to verify all types that have finite number of distinct
states such as communications protocols for secure exchange of
information.

2/16/2023 Dakhole Dipali K 16

Applications of Push Down Automata
➢ For designing the parsing phase of a compiler (Syntax
Analysis).
➢ For implementation of stack applications.
➢ For evaluating the arithmetic expressions.
➢ For solving the Tower of Hanoi Problem.

2/16/2023 Dakhole Dipali K 17

 Applications of Turing machine

➢ For solving any recursively enumerable problem.

➢ For understanding complexity theory.
➢ For implementation of neural networks.
➢ For implementation of Robotics Applications.
➢ For implementation of artificial intelligence.

2/16/2023 Dakhole Dipali K 18

General Concepts of Automata Theory
• Symbol
• Alphabet
• Strings
• Empty Strings
• Length of the string
• Power of an Alphabet
• Concatenation of two strings
• Languages

2/16/2023 Dakhole Dipali K

19
Alphabets and Strings
• Symbol: a, b, 1 ,2, 3, 0, etc.

• We will use small alphabets:  = a, b

• Strings a
ab u = ab
abba
v = bbbaaa
baba
aaabbbaabab w = abba

2/16/2023 Dakhole Dipali K

20
 String Operations

w = a1a2  an abba
v = b1b2 bm bbbaaa

1. Concatenation

wv = a1a2  anb1b2 bm abbabbbaaa

2/16/2023 Dakhole Dipali K

21
[Link]
w = a1a2  an ababaaabbb
w R = an  a2 a1 bbbaaababa
3. String Length
w = a1a2  an Examples:
abba = 4
Length: w =n aa = 2
a =1

2/16/2023 Dakhole Dipali K 22

4. Length of Concatenation
uv = u + v
• Example:
u = aab, u =3
v = abaab, v =5

uv = aababaab = 8
uv = u + v = 3 + 5 = 8

2/16/2023 Dakhole Dipali K

23
5. Empty String
• A string with no letters:  or ϵ

• Observations:
 =0

w = w = w

abba = abba = abba

2/16/2023 Dakhole Dipali K

24
 6. Substring
• Substring of string:
• a subsequence of consecutive characters
String Substring
abbab ab
abbab abba
abbab b
abbab bbab

2/16/2023 Dakhole Dipali K

25
7. Prefix and Suffix
abbab
Prefixes Suffixes
 abbab w = uv
a bbab
ab bab prefix
abb ab suffix
abba b
abbab 

2/16/2023 Dakhole Dipali K

26
8. Another Operation
n
w = ww

 
w
n

• Example: (abba ) = abbaabba

2

• Definition: w0 = 
(abba )0 = 

2/16/2023 Dakhole Dipali K

27
9. The * Operation

 * the set of all possible strings from  alphabet

 = a, b
* =  , a, b, aa, ab, ba, bb, aaa, aab,

2/16/2023 Dakhole Dipali K

28
10. The + Operation
+ : the set of all possible strings from

alphabet  except 
 = a, b
* =  , a, b, aa, ab, ba, bb, aaa, aab,
+
 =  * −
+
 = a, b, aa, ab, ba, bb, aaa, aab,

2/16/2023 Dakhole Dipali K 29

Languages
• A language is a set of strings

• String: A sequence of letters

• Examples: “cat”, “dog”, “house”, …

• Defined over an alphabet:

 = a, b, c,, z

2/16/2023 Dakhole Dipali K

30
• A language is any subset of  *

• Example:
 = a, b
* =  , a, b, aa, ab, ba, bb, aaa,
• Languages:
 
a, aa, aab
{ , abba, baba, aa, ab, aaaaaa}

2/16/2023 Dakhole Dipali K

31
 Note that

Sets  = { }  {}
Set size {} =  = 0
Set size {} = 1
String length  =0

2/16/2023 Dakhole Dipali K 32

Another Example
An infinite language
L = {a b : n  0}
n n


ab
L abb  L
aabb
aaaaabbbbb

2/16/2023 Dakhole Dipali K

33
Operations on Languages
1. The usual set operations
a, ab, aaaa  bb, ab = {a, ab, bb, aaaa}
a, ab, aaaa  bb, ab = {ab}
a, ab, aaaa − bb, ab = a, aaaa
Complement: L =  * −L
a, ba =  , b, aa, ab, bb, aaa,

2/16/2023 Dakhole Dipali K

34
 2. Reverse
Definition:
L = {w : w  L}
R R

Examples:
ab, aab, baba = ba, baa, abab
R

L = {a b : n  0}
n n

LR
= {b a : n  0}
n n

2/16/2023 Dakhole Dipali K

35
[Link]

• Definition: L1L2 = xy : x  L1, y  L2 

• Example: a, ab, bab, aa

= ab, aaa, abb, abaa, bab, baaa

2/16/2023 Dakhole Dipali K

36
 4. Another Operation
• Definition: Ln =  
LLL
n

a, b = a, ba, ba, b =

3

aaa, aab, aba, abb, baa, bab, bba, bbb

L0 = 
• Special case:
a , bba , aaa 0 = 

2/16/2023 Dakhole Dipali K

37
More Examples

L = {a b : n  0}
n n

L = {a b a b : n, m  0}
2 n n m m

2
aabbaaabbb L

2/16/2023 Dakhole Dipali K

38
5. Star-Closure (Kleene *)
Definition:
L* = L  L  L 
0 1 2

 , 
• Example:
a, bb, 
 
a, bb* =  
 aa , abb, bba , bbbb, 
aaa, aabb, abba, abbbb,

2/16/2023 Dakhole Dipali K

39
6. Positive Closure (Kleene Plus)

+
Definition:
L = L  L 
1 2

= L * −
a, bb, 
+  
a, bb = aa, abb, bba, bbbb, 
aaa, aabb, abba, abbbb,
 
2/16/2023 Dakhole Dipali K
40