UNIT –1 AUTOMATA FUNDAMENTALS
INTRODUCTION
The study of abstract devicea is the called automata theory.
Finite Automata is a mathematical model that accepts a set of inputs, process
through a set of states, generates an output.
Automation helps in
o Designin and checking the behavior of digital circuits
o Pattern searching in websites
o Verifying systems like communication protocols for secure data transfers
o Designing lexical analyzers in compliers
Finite automation model is a study of machines.
History
Alan Turing introduced an abstract machine in 1930‟s. This machine had all the
,capabilities of today‟s computer.
In 1940‟s and 1950‟s, the machines were simplified to finite automation machines.
Researchers proposed the automation model in order to model the functions of human brain.
The linguist Noam Chomsky made a study on formal grammars in late 1950‟s .These
grammars provided the basis of compliers.
S.Cook extended Turing‟s study in 1969, which separated the problems as solvable
and unsolvable. He classified problems as NP-Hard and as NP-Complete.
Example of a Finite state system: Switch operation
PUSH
Start
OFF ON
PUSH
,
, Theory of Computation
Here,
When the electric switch = “ON” indicates logic „1‟ when pushed from startstate.
Goes to „OFF‟ state when pushed from „ON‟ state.
Example: Pattern searching of sting = “then”
t h e n
t th the then
Example: Pattern searching of sting = “automata
a u t o m a t
a au aut auto autom automa automat
a automata
BASIC MATHEMATICAL NOTATION AND TECHNIQUES
Basic Mathematical
Objects Sets [A]
A set is collection of elements of finite number.
Example:
A = {10, 01, 00, 11}
B = {w | w is a set of prime numbers less than 100}
wB
C = {r | r is a set of strings generated from vowels}
rC
Subset [ ]
Let A1and A2 are two sets, then A1 is a subset of A2 [indicated as A1 A2 ], if every
element of A1 is in A2.
Example:
A1 = {1, 2, 3, 4}
A2 = {1, 2, 3, 4, 5}
A1 A2
INTRODUCTION
The study of abstract devicea is the called automata theory.
Finite Automata is a mathematical model that accepts a set of inputs, process
through a set of states, generates an output.
Automation helps in
o Designin and checking the behavior of digital circuits
o Pattern searching in websites
o Verifying systems like communication protocols for secure data transfers
o Designing lexical analyzers in compliers
Finite automation model is a study of machines.
History
Alan Turing introduced an abstract machine in 1930‟s. This machine had all the
,capabilities of today‟s computer.
In 1940‟s and 1950‟s, the machines were simplified to finite automation machines.
Researchers proposed the automation model in order to model the functions of human brain.
The linguist Noam Chomsky made a study on formal grammars in late 1950‟s .These
grammars provided the basis of compliers.
S.Cook extended Turing‟s study in 1969, which separated the problems as solvable
and unsolvable. He classified problems as NP-Hard and as NP-Complete.
Example of a Finite state system: Switch operation
PUSH
Start
OFF ON
PUSH
,
, Theory of Computation
Here,
When the electric switch = “ON” indicates logic „1‟ when pushed from startstate.
Goes to „OFF‟ state when pushed from „ON‟ state.
Example: Pattern searching of sting = “then”
t h e n
t th the then
Example: Pattern searching of sting = “automata
a u t o m a t
a au aut auto autom automa automat
a automata
BASIC MATHEMATICAL NOTATION AND TECHNIQUES
Basic Mathematical
Objects Sets [A]
A set is collection of elements of finite number.
Example:
A = {10, 01, 00, 11}
B = {w | w is a set of prime numbers less than 100}
wB
C = {r | r is a set of strings generated from vowels}
rC
Subset [ ]
Let A1and A2 are two sets, then A1 is a subset of A2 [indicated as A1 A2 ], if every
element of A1 is in A2.
Example:
A1 = {1, 2, 3, 4}
A2 = {1, 2, 3, 4, 5}
A1 A2
