Scribd
Upload
4 views56 pages

Understanding Deterministic Finite Automata

The document explains the concept of Deterministic Finite Automata (DFA), detailing its components such as states, input alphabet, transition function, initial state, and accepting states. It describes how DFAs accept or reject input strings based on the transitions and the final state after scanning the entire input. Additionally, it introduces the concept of regular languages, which are defined as languages accepted by DFAs.

Uploaded by

GSS-CSE PSG CT
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
4 views56 pages

Understanding Deterministic Finite Automata

The document explains the concept of Deterministic Finite Automata (DFA), detailing its components such as states, input alphabet, transition function, initial state, and accepting states. It describes how DFAs accept or reject input strings based on the transitions and the final state after scanning the entire input. Additionally, it introduces the concept of regular languages, which are defined as languages accepted by DFAs.

Uploaded by

GSS-CSE PSG CT
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Deterministic

Finite
Automata
Deterministic Finite Automaton
(DFA)
⚫ Input
Tape
String
Outpu
t
“Accept
Finite ”
Automato or
n “Reject
”
Transition Graph
⚫

initia
l accepting
transitio
state state
stat n
e
Alphabe
t
⚫

For every state, there is a


transition
for every symbol in the alphabet
hea
d Initial Configuration
Input
a ⚫
Tape

Input
String

Initial state
Scanning the Input
⚫
⚫
⚫
Input finished

accep
t
A Rejection
Case
⚫

Input
String
⚫
⚫
Input finished

reject
Another Rejection
Case
Tape is
⚫ empty
Input
Finished

reject
Language
Accepted:
⚫
To accept a
string:
all the input string is
scanned
and the last state is
accepting

To reject a
string:
all the input string is scanned
and the last state is non-
accepting
Another Example
⚫

Accep Accep Accep


t t t
Empty
Tape
Input
Finished

accep
t
Another Example

Accept trap
state state
Input
String
Input finished

accep
t
A rejection
case

Input
String
Input finished

reject
Language
Accepted:
Another Example

Alphabet
:

Language
Accepted:
Formal Definition
⚫ Deterministic Finite Automaton (DFA)

: set of
states
: input
alphabet
: transition X 
function
: initial
state
: set of accepting
states
Set of States
⚫ Exampl
e
Input Alphabet
:the input alphabet never
⚫
contains
Exampl
e
Initial State
⚫
Exampl
e
Set of Accepting States
⚫
Exampl
e
Transition Function
⚫

Describes the result of a


transition
from state with symbol
Exampl
⚫
e:
Transition Table for

symbol
⚫ s
states
Extended Transition Function
⚫

Describes the resulting state


after scanning string from
state
⚫
Exampl
e:
Special
case:

for any
state
In
general:
implies that there is a walk of
transitions

states may be
repeated
Language Accepted by DFA

Language of DFA
:
it is denoted as and
contains
all the strings accepted by

We say that a language

is accepted (or
recognized)
⚫For a DFA

⚫Language accepted by :

⚫
⚫Language rejected by :
More DFA Examples

Empty All
language strings
Language of the empty
string
= { all strings with prefix
⚫
}

accep
t
= { all binary strings
⚫
containing
substring }
= { all binary strings
⚫
without
substring }
⚫
Regular Languages
⚫Definition:
⚫A language is regular if there is
a DFA that accepts it )

⚫The languages accepted by all DFAs


form the family of regular languages
Example regular
languages:

{ all strings in {a,b}* with prefix


}
{ all binary strings without substring
}

There exist automata that accept


these

You might also like