PPT: Finite Automata Notes | EduRev

Theory of Computation

Computer Science Engineering (CSE) : PPT: Finite Automata Notes | EduRev

 Page 1


1
Finite Automata
Page 2


1
Finite Automata
2
Finite Automaton (FA)
n Informally, a state diagram that comprehensively
captures all possible states and transitions that a
machine can take while responding to a stream or
sequence of input symbols
n Recognizer for “Regular Languages”
n Deterministic Finite Automata (DFA)
n The machine can exist in only one state at any given time
n Non-deterministic Finite Automata (NFA)
n The machine can exist in multiple states at the same time
Page 3


1
Finite Automata
2
Finite Automaton (FA)
n Informally, a state diagram that comprehensively
captures all possible states and transitions that a
machine can take while responding to a stream or
sequence of input symbols
n Recognizer for “Regular Languages”
n Deterministic Finite Automata (DFA)
n The machine can exist in only one state at any given time
n Non-deterministic Finite Automata (NFA)
n The machine can exist in multiple states at the same time
3
Deterministic Finite Automata
- Definition
n A Deterministic Finite Automaton (DFA)
consists of:
n Q ==> a finite set of states
n ? ==> a finite set of input symbols (alphabet)
n q
0
==> a start state
n F ==> set of accepting states
n d ==> a transition function, which is a mapping
between Q x ? ==> Q
n A DFA is defined by the 5-tuple:
n {Q, ? , q
0
,F, d }
Page 4


1
Finite Automata
2
Finite Automaton (FA)
n Informally, a state diagram that comprehensively
captures all possible states and transitions that a
machine can take while responding to a stream or
sequence of input symbols
n Recognizer for “Regular Languages”
n Deterministic Finite Automata (DFA)
n The machine can exist in only one state at any given time
n Non-deterministic Finite Automata (NFA)
n The machine can exist in multiple states at the same time
3
Deterministic Finite Automata
- Definition
n A Deterministic Finite Automaton (DFA)
consists of:
n Q ==> a finite set of states
n ? ==> a finite set of input symbols (alphabet)
n q
0
==> a start state
n F ==> set of accepting states
n d ==> a transition function, which is a mapping
between Q x ? ==> Q
n A DFA is defined by the 5-tuple:
n {Q, ? , q
0
,F, d }
4
What does a DFA do on
reading an input string?
n Input: a word w in ?*
n Question: Is w acceptable by the DFA?
n Steps:
n Start at the “start state” q
0
n For every input symbol in the sequence w do
n Compute the next state from the current state, given the
current input symbol in w and the transition function
n If after all symbols in w are consumed, the current
state is one of the accepting states (F) then accept
w;
n Otherwise, reject w.
Page 5


1
Finite Automata
2
Finite Automaton (FA)
n Informally, a state diagram that comprehensively
captures all possible states and transitions that a
machine can take while responding to a stream or
sequence of input symbols
n Recognizer for “Regular Languages”
n Deterministic Finite Automata (DFA)
n The machine can exist in only one state at any given time
n Non-deterministic Finite Automata (NFA)
n The machine can exist in multiple states at the same time
3
Deterministic Finite Automata
- Definition
n A Deterministic Finite Automaton (DFA)
consists of:
n Q ==> a finite set of states
n ? ==> a finite set of input symbols (alphabet)
n q
0
==> a start state
n F ==> set of accepting states
n d ==> a transition function, which is a mapping
between Q x ? ==> Q
n A DFA is defined by the 5-tuple:
n {Q, ? , q
0
,F, d }
4
What does a DFA do on
reading an input string?
n Input: a word w in ?*
n Question: Is w acceptable by the DFA?
n Steps:
n Start at the “start state” q
0
n For every input symbol in the sequence w do
n Compute the next state from the current state, given the
current input symbol in w and the transition function
n If after all symbols in w are consumed, the current
state is one of the accepting states (F) then accept
w;
n Otherwise, reject w.
5
Regular Languages
n Let L(A) be a language recognized by a
DFA A.
n Then L(A) is called a “Regular Language”.
n Locate regular languages in the
Chomsky Hierarchy
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

Extra Questions

,

Sample Paper

,

PPT: Finite Automata Notes | EduRev

,

Free

,

Viva Questions

,

mock tests for examination

,

Objective type Questions

,

MCQs

,

video lectures

,

PPT: Finite Automata Notes | EduRev

,

Summary

,

ppt

,

Semester Notes

,

Previous Year Questions with Solutions

,

past year papers

,

Exam

,

shortcuts and tricks

,

PPT: Finite Automata Notes | EduRev

,

study material

,

practice quizzes

,

pdf

,

Important questions

;