Scribd
Upload
29 views20 pages

TOA Handout-1

Uploaded by

waseem khosa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
29 views20 pages

TOA Handout-1

Uploaded by

waseem khosa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 20

INTRODUCTION

Introduction

 Psychologists, mathematicians, engineers


and some of the first computer scientists
shared a common interest:
– To model the human thought process.
– Whether in the brain or in a computer.

 Warren McCulloch and Walter Pitts, two


neurophysiologists, were the first to
present a description of finite automata in
1943.
Objective of the Course
• This course is about the fundamental
capabilities and limitations of computers.
• This theory is very much relevant to
practice, for example, in the design of
new programming languages, compilers,
string searching, etc., etc.
• This course helps you to learn problem
solving skills.
• Theory teaches you how to think, express
and solve problems,.
Cont….
• Every time we introduce a new machine, we
will learn its language; and every time we
develop a new language, we will try to find
a machine that corresponds to it.
• In particular, the way we shall be studying
about computers is to build mathematical
models, called machines, and then to study
their limitations by analyzing the types of
inputs on which they can operate
successfully.
• The collection of these successful inputs is
called the language of the machine
Automata Theory
 Automata theory is the study of:
• Abstract machines (or more appropriately,
abstract 'mathematical' machines or systems)
• And the computational problems that can be
solved using these machines.
 These abstract machines are called automata.
• Automata is Greek letters .Automata is a word
formulated from automation, which means
machine designing or replacing human beings
with machines
It is the plural of automaton, and it means
“something that works automatically”.
 An automaton can be a finite representation of a
formal language that may be an infinite set.
Mathematical Preliminaries

6
SETS
• Definition: A set is well defined collection of
objects, which are
• unordered
• distinct
• same type
• with common properties
• Sets are written with curly braces {}, and the
elements in the set are written within the curly
braces.
• The set {a, b, c} has elements a, b, and c.
• The sets {a, b, c} and {b, c, b, a, a} are the same
since order does not matter in a set and since
redundancy does not count.
• The set {a} has element a. Note that {a} and a are
different things; {a} is a set with one element a.
• The set {xn : n = 1, 2, 3, . . .} consists
of x, xx, xxx, . . ..
• The set of positive even numbers is {2,
4, 6, 8, 10, 12, . . .} = {2n : n =1, 2, 3, .
. .}.
• The set of odd numbers is {1, 3, 5, 7, 9,
11, 13, . . .} = {2n + 1 : n = 0, 1,
2, . . .}.
Set Representations

C = { a, b, c, d, e, f, g, h, i, j, k }

C = { a, b, …, k } finite set

S = { 2, 4, 6, … } infinite set

S = { j : j > 0, and j = 2k for some


k>0 }

S = { j : j is nonnegative and even }


Courtesy Costas Busch - RPI 9
A = { 1, 2, 3, 4, 5 }
U
6 A
2 3 8
1
7 4 5
9
10

Universal Set: all possible elements

U = { 1 , … , 10 }
10
Set Operations
A = { 1, 2, 3 } B = { 2, 3, 4, 5}
A B
• Union
2 4
1
3
A U B = { 1, 2, 3, 4, 5 } 5

• Intersection
U
A B = { 2, 3 } 2
3
• Difference
A-B={1}
1
B - A = { 4, 5 }
Venn diagrams
Courtesy Costas Busch - RPI 11
• Complement
Universal set = {1, …, 7}
A = { 1, 2, 3 } A = { 4, 5, 6, 7}

4
A
A 3 6
1
2
5 7

A=A
12
{ even integers } = { odd
integers }

Integers

1 odd
even 5
2 6
0
4
3 7

13
DeMorgan’s Laws

U
AUB=A B

U
A B=AUB

14
Empty, Null Set:
={}

SU =S
U
S = = Universal Set

S- =S

-S=

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

U
Proper Subset: A B

U
B
A

16
Disjoint Sets
A = { 1, 2, 3 } B = { 5, 6}

U
A B=

A B

17
Set Cardinality
• For finite sets
A = { 2, 5, 7, 1, 10 }

|A| = 5

(set size)

18
Powersets
A powerset is a set of sets

S = { a, b, c }

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

={ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c

Observation: | 2S | = 2|S| ( 8 = 23 )

19
Cartesian Product
A = { 2, 4 } B = { 2, 3, 5 } C={ 7,8}

A X B = { (2, 2), (2, 3), (2, 5), ( 4, 2), (4, 3), (4, 5) }

|A X B| = |A| |B|

Generalizes to more than two sets

AXBX…XZ
20

You might also like