Automata

Introduction to
Automata Theory
What is Automata Theory?
Automata theory is a branch of theoretical computer science and mathematics that deals with
the study of abstract machines and formal languages. It provides a framework for
understanding and analyzing the behavior of computational devices, often referred to as
automata, which can simulate processes, recognize patterns, and perform computations.
Automata theory is particularly concerned with the design, classification, and analysis of
automata models that mimic the operation of various computing devices. These automata
models are used to describe the computational capabilities of different systems and to explore
the limits of computation.
What is Automata Theory?
Examples of Automata Theory
● Sequential Machine
● Vending Machine
● Traffic Lights
● Video Games
● Text Parsing
● Regular Expression Matching
● Speech Recognition
Characteristic of Automata
● Input - It is a finite set of input symbols or sequences of symbols, {x1,
x2, x3,...xk}, where k is the number of inputs.
● Output - It is a finite set of output symbols, {y1, y2, y3,...ym}, where m

is the number of outputs.
● State - It is a finite set, denoted by Q whose definition depends on the

type of automaton.
Theory of Computation (Finite
Automata)
What is Finite Automata?

The Finite Automata is the simplest machine which is used to recognize
patterns. It has a finite set of states with which it accepts or rejects strings. It is
an abstract machine which has five elements or tuples. It is good for devices
which have an extremely limited amount of memory. It has a set of states and
rules for moving from one state to another, but it relies upon the applied input
symbol. It has finite memory and an input tape. The machine accepts the input
if it is in the accepting state at the end of the string; otherwise, it rejects the
input.
Deterministic Finite Automaton (DFA)
What is DFA?
In DFA, for each input symbol, one can determine the state
to which the machine will move. Hence, it is called
Deterministic Automaton. As it has a finite number of
states, the machine is called Deterministic Finite Machine
or Deterministic Finite Automaton.
Examples of DFA?
Examples of DFA?
Non-Deterministic Finite
Automaton (DFA)
What is Non-DFA?
In NDFA, for a particular input symbol, the machine can move to any
combination of the states in the machine. In other words, the exact state to
which the machine moves cannot be determined. Hence, it is called Non-
deterministic Automaton. As it has finite number of states, the machine is
called Non-deterministic Finite Machine or Non-deterministic Finite
Automaton.
Examples of Non-DFA?
Examples of Non-DFA?
Difference between DFA and
NDFA
S. DFA NFA
No.
1. For Every symbol of the alphabet, there is We do not need to specify how does the
only one state transition in DFA. NFA react according to some symbol.
2. DFA cannot use Empty String transition. NFA can use Empty String transition.
3. DFA can be understood as one machine. NFA can be understood as multiple little
machines computing at the same time.
4. DFA will reject the string if it end at other If all of the branches of NFA dies or
than accepting state. rejects the string, we can say that NFA
reject the string.
5. Backtracking is allowed in DFA. Backtracking is not always allowed in NFA.
6. DFA can be understood as one machine. NFA can be understood as multiple little
machines computing at the same time.
7. DFA will reject the string if it end at other than If all of the branches of NFA dies or rejects the
accepting or final state. string, we can say that NFA reject the string.
8. DFA is more difficult to construct. NFA is easier to construct.
9.
DFA vs NDFA
DFA vs NDFA
S. Title NFA DFA

No.
1. Power Same Same
2. Supremacy Not all NFA are DFA. All DFA are NFA
3. Transition Maps Q → (∑∪{λ}→2Q), the number of Q × ∑→Q, the number

Function next states is zero or one or more. of next states is exactly
one
4. Time complexity The time needed for executing an input The time needed for
string is more as compare to DFA. executing an input
string is less as
compare to NFA.
5. Space Less space requires. More space requires.

Automata

Uploaded by

Copyright:

Available Formats

Automata

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Automata

Uploaded by

Copyright:

Available Formats

Introduction to

● Output - It is a finite set of output symbols, {y1, y2, y3,...ym}, where m

● State - It is a finite set, denoted by Q whose definition depends on the

What is Finite Automata?

8. DFA is more difficult to construct. NFA is easier to construct.

S. Title NFA DFA

1. Power Same Same

3. Transition Maps Q → (∑∪{λ}→2Q), the number of Q × ∑→Q, the number

5. Space Less space requires. More space requires.

You might also like