PPT: Finite Automata Notes | EduRev

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

The document PPT: Finite Automata Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
 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

Related Searches

study material

,

PPT: Finite Automata Notes | EduRev

,

Sample Paper

,

shortcuts and tricks

,

Exam

,

Free

,

Semester Notes

,

Objective type Questions

,

MCQs

,

PPT: Finite Automata Notes | EduRev

,

Important questions

,

ppt

,

mock tests for examination

,

Viva Questions

,

Previous Year Questions with Solutions

,

Summary

,

practice quizzes

,

pdf

,

video lectures

,

PPT: Finite Automata Notes | EduRev

,

Extra Questions

,

past year papers

;