1 of 49

Session-1and 2:�Basic Mathematical Notation and techniques

By

Dr. Ashok Kumar

Amity School of Engineering & Technology

2 of 49

Introduction to Automata Theory

Automata theory is a branch of computer science and mathematics that deals with the study of abstract machines and computational models.
Concerned with the study of the fundamental principles of computation, their limitations, and their capabilities.
Automata are used to describe and analyse various computational processes, such as the behavior of computer programs and the recognition of patterns in text or other data.
Networks of automata are designed to mimic human behaviour

Amity School of Engineering & Technology

3 of 49

Basic Mathematical Notation and techniques

Amity School of Engineering & Technology

4 of 49

Basic Mathematical Notation and techniques

Amity School of Engineering & Technology

5 of 49

String Operations

5

Concatenation

Amity School of Engineering & Technology

6 of 49

6

Reverse

Amity School of Engineering & Technology

7 of 49

String Length

Length:

Examples:

7

Amity School of Engineering & Technology

8 of 49

Length of Concatenation

Example:

8

Amity School of Engineering & Technology

9 of 49

Empty String

A string with no letters:

Observations:

9

Amity School of Engineering & Technology

10 of 49

Substring

Substring of string:

a subsequence of consecutive characters

String Substring

10

Amity School of Engineering & Technology

11 of 49

Prefix and Suffix

Prefixes Suffixes

11

prefix

suffix

Amity School of Engineering & Technology

12 of 49

Another Operation

Example: (ab)⁴ = abababab

Definition:

12

Amity School of Engineering & Technology

13 of 49

The * Operation

13

Amity School of Engineering & Technology

14 of 49

14

The + Operation

Amity School of Engineering & Technology

15 of 49

Languages

15

Amity School of Engineering & Technology

16 of 49

16

Note that:

Sets

Set size

String length

Amity School of Engineering & Technology

17 of 49

Another Example

An infinite language

17

Amity School of Engineering & Technology

18 of 49

Operations on Languages

The usual set operations

Complement:

18

Amity School of Engineering & Technology

19 of 49

Reverse

Definition:

Examples:

19

Amity School of Engineering & Technology

20 of 49

Concatenation

Definition:

Example:

20

Amity School of Engineering & Technology

21 of 49

Another Operation

Definition:

Special case:

21

{a, b}³={a,b}{a,b}{a,b}=

{aaa,aab,aba,abb,baa,bab,bba,bbb}

Amity School of Engineering & Technology

22 of 49

More Examples

22

aabb∈L

Amity School of Engineering & Technology

23 of 49

Star-Closure (Kleene *)

Definition:

Example:

23

Amity School of Engineering & Technology

24 of 49

Positive Closure

Definition:

24

Amity School of Engineering & Technology

25 of 49

25

Mathematical Preliminaries

Sets
Functions
Relations
Graphs
Proof Techniques

Amity School of Engineering & Technology

26 of 49

26

A set is a collection of elements

SETS

We write

Amity School of Engineering & Technology

27 of 49

27

A = { 1, 2, 3, 4, 5 }

Universal Set: all possible elements

U = { 1 , … , 10 }

1

2

3

4

5

A

U

6

7

8

9

10

Amity School of Engineering & Technology

28 of 49

28

Set Operations

A = { 1, 2, 3 } B = { 2, 3, 4, 5}

Union

A U B = { 1, 2, 3, 4, 5 }

Intersection

A B = { 2, 3 }

Difference

A - B = { 1 }

B - A = { 4, 5 }

U

A

B

2

3

1

4

5

2

3

1

Venn diagrams

Amity School of Engineering & Technology

29 of 49

29

A

Complement

Universal set = {1, …, 7}

A = { 1, 2, 3 } A = { 4, 5, 6, 7}

1

2

3

4

5

6

7

A

A = A

Amity School of Engineering & Technology

30 of 49

30

0

2

4

6

1

3

5

7

even

{ even integers } = { odd integers }

odd

Integers

Amity School of Engineering & Technology

31 of 49

31

DeMorgan’s Laws

A U B = A B

U

A B = A U B

U

Amity School of Engineering & Technology

32 of 49

32

Empty, Null Set:

= { }

S U = S

S =

S - = S

- S =

U

= Universal Set

Amity School of Engineering & Technology

33 of 49

33

Subset

A = { 1, 2, 3} B = { 1, 2, 3, 4, 5 }

A B

U

Proper Subset:

A B

U

A

B

Set A is considered to be a proper subset of Set B if Set B contains at least one element that is not present in Set A.

Amity School of Engineering & Technology

34 of 49

34

Disjoint Sets

A = { 1, 2, 3 } B = { 5, 6}

A B =

U

A

B

Amity School of Engineering & Technology

35 of 49

35

Set Cardinality

For finite sets

A = { 2, 5, 7 }

|A| = 3

Amity School of Engineering & Technology

36 of 49

36

Powersets

A powerset is a set of all subsets

Powerset of S = the set of all the subsets of S

S = { a, b, c }

2^S = { , , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

Observation: | 2^S | = 2^|S| ( 8 = 2³)

Amity School of Engineering & Technology

37 of 49

37

FUNCTIONS

domain

1

2

3

a

b

c

range

f : A -> B

A

B

f(1) = a

4

5

Amity School of Engineering & Technology

38 of 49

38

Let A & B be sets. A binary relation “R” from A to B

R = {(x₁, y₁), (x₂, y₂), (x₃, y₃), …}

Where and

R ⊆ A x B

x_i R y_i to denote

e. g. if R = ‘>’: 2 > 1, 3 > 2, 3 > 1

RELATIONS

Amity School of Engineering & Technology

39 of 49

39

GRAPHS

A directed graph

Nodes (Vertices)

V = { a, b, c, d, e }

Edges

E = { (a,b), (b,c), (b,e),(c,a), (c,e), (d,c), (e,b), (e,d) }

node

edge

a

b

c

d

e

Amity School of Engineering & Technology

40 of 49

40

Labeled Graph

a

b

c

d

e

1

3

5

6

2

6

2

Amity School of Engineering & Technology

41 of 49

41

PROOF TECHNIQUES

Proof by induction

Proof by contradiction

Amity School of Engineering & Technology

42 of 49

42

Induction

We have statements P₁, P₂, P₃, …

If we know

for some b that P₁, P₂, …, P_b are true
for any k >= b that

P₁, P₂, …, P_k imply P_k+1

Then

Every P_i is true

Amity School of Engineering & Technology

43 of 49

43

Proof by Induction

Inductive basis

Find P₁, P₂, …, P_b which are true

Inductive hypothesis

Let’s assume P₁, P₂, …, P_k are true,

for any k >= b

Inductive step

Show that P_k+1 is true

Amity School of Engineering & Technology

44 of 49

44

Example

Theorem: A binary tree of height h has at most 2^h leaves.

Proof by induction:

let L(i) be the maximum number of

leaves of any subtree at height i

Amity School of Engineering & Technology

45 of 49

45

We want to show: L(i) <= 2ⁱ

Inductive basis
L(0) = 1 (the root node)

Inductive hypothesis

Let’s assume L(i) <= 2ⁱ for all i = 0, 1, …, k

Induction step

we need to show that L(k + 1) <= 2^k+1

Amity School of Engineering & Technology

46 of 49

46

L(k) <= 2^k

L(k+1) <= 2 * L(k) <= 2 * 2^k = 2^k+1

Induction Step

height

k

k+1

(we add at most two nodes for every leaf of level k)

Amity School of Engineering & Technology

47 of 49

47

Proof by Contradiction

We want to prove that a statement P is true

we assume that P is false
then we arrive at an incorrect conclusion
therefore, statement P must be true

Amity School of Engineering & Technology

48 of 49

48

Example

Theorem: is not rational

Proof:

Assume by contradiction that it is rational

= n/m

n and m have no common factors

We will show that this is impossible

Amity School of Engineering & Technology

49 of 49

49

= n/m 2 m² = n²

Therefore, n² is even

n is even

n = 2 k

2 m² = 4k²

m² = 2k²

m is even

m = 2 p

Thus, m and n have common factor 2

Contradiction!

Amity School of Engineering & Technology