FINITE AUTOMATA?

A finite automata (FA) is a simple idealized machine

used to recognize patterns within input taken from some
character set (or alphabet). The job of an FA is to accept
or reject an input depending on whether the pattern
defined by the FA occurs in the input. A finite
automaton consists of: a finite sets of N states.

06/25/22 TOA 1
 FINITE AUTOMATA EXAMPLE

Elevators
Vending Machines
String Matching

06/25/22 TOA 2
FINITE AUTOMATA
Language Recognizers
Machines embedded with grammatical rules that
recognize a language
Automated language recognition
REs define a language and FAs accept (or reject )
them
FAs serve two purposes
 Implicit language definition
 Recognition
FINITE AUTOMATA

Visual notations (abstract machines)

Sort of graphs consisting of nodes called states and edges

called transitions

States serve as memory locations that keep a track of last

character read

Transitions define where to go on reading a particular character

FINITE AUTOMATON

A finite automaton is a collection of three things

A finite set of states

Exactly one initial state (start state)
One or more (may be none) final states that mark
the acceptance of a word
Intermediate states that are neither start not final
states
An alphabet  of possible input letters
FINITE AUTOMATON

 A finite set of transitions that tell for each state and for each letter of the input
alphabet which state to go to next
FINITE AUTOMATON
The start state marks the beginning of reading every
input
Reading a character triggers a transition from that state
which may transfer control to some other state and the
reading mechanism advances to next character and the
process continues
When the input terminates, if the control is left with a
final or accepting state, the input string is accepted
otherwise it is rejected and the FA resets control to the
initial state for next input
FINITE AUTOMATON
The state to go to next on reading a letter of the input

string is determined automatically and deterministically

by the transitions and is fixed (for that particular state

and input character)

The transitions are fired automatically

A single character is consumed for each transition

FINITE AUTOMATON

Visual representations
 States represented by circles labeled to identify each distinctly

 Initial (- sign) and Final states (+ sign )

1
 Transitions
 Directed edges labeled with the characters of 
FINITE AUTOMATA
Example
 Language of all words that end at b

a
b
b
-1 +2

a
CHARACTERISTICS OF FA

Every FA must have exactly one start state

There may be multiple or may be no final states
 In the latter case the FA doesn’t accept any language

Only a single character is read on a state at a time

CHARACTERISTICS OF FA

Every state define a transition for every character

in the alphabet set or alternatively every state has
exactly as many outgoing transitions as the
number of characters in , each labeled with a
distinct letter from 
 No duplicate edges
 No missing edges
CHARACTERISTICS OF FA

An FA is built for a particular language and

recognizes only that language

It should accept all valid words of the language

It should reject all invalid words of the language

EXAMPLES
All words that contain even number of letters
All words ending with ab
All words that start with a
All words of length >=3
All words that don’t end at ba
All words that contain a triple letter either aaa or
bbb
06/25/22 TOA 15
06/25/22 TOA 16
 FINITE AUTOMATA

06/25/22 TOA 17
 FINITE AUTOMATA

06/25/22 TOA 18
 FINITE AUTOMATA

06/25/22 TOA 19
 FINITE AUTOMATA

06/25/22 TOA 20
 FINITE AUTOMATA

06/25/22 TOA 21
 FINITE AUTOMATA

06/25/22 TOA 22
 DESIGN FINITE AUTOMATA
Given some language, design a finite automaton
that recognizes it.
• A = {w| w contains the string 001 as a substring}
• 001, 010001, 11100101 are all in the language
• 0101, 11100, 0000 are not.
• “Think as an automaton”
1. As symbols come in, initially skip over all 1s.
2. As a 0 comes in, it might be the first of the substring 001
3. If a 1 comes in, go back to skipping over 1s; if a 0 comes in,
it might be the second of the substring 001
4. If a 1 comes in, we see the substring, if a 0 comes in, it
might be the second of the substring

06/25/22 TOA 23
LANGUAGES OF FA

FAs define Regular Language

Any language that can be define by a regular

expression can be recognized by an FA
 NFAS AND
TRANSITION Chapter 6

GRAPHS
DETERMINISTIC FA (DFA)

The FAs that we have studied so far are DFA in that

 At every state there is exactly one outgoing transition for a character and the
machine can follow the transition deterministically
 No duplicates

 No missing edges
NFA
Reduces number of states and transitions

Costly execution
 Needs concurrent processing to find a successful path

An NFA can have a successful and unsuccessful path for the

same input

If an NFA has at least one successful path for an input it is

considered to be valid

Machine crashes for an undefined transition thus causing implicit

reject
NFA LANGUAGE
RECOGNITION
Acceptance
 If at least one successful path exists

Rejection
 Either machine crashes on input or ]
 No successful path exists
NFA
Examples
 An NFA that accepts the language {bb, bbb}

 All words that contain bb in them

 All words contains a double letter

EPSILON TRANSITIONS

ε- Transitions

A null transition that changes state but doesn’t consume any

character

Possible with NFAs and Transition Graphs (discussed next)

 NFA
Alphabet = {a}

q1 a q2
a
Start
q0
a
q3
 Example: Accepting

a a

q1 a q2
a
Start
q0
a
q3
 Example: Accepting

a a

First choice q1 a q2
a
Start
q0
a
Parallel Processing
Second choice q3
 Example: Accepting

a a

q1 a q2
a
Start
q0
a
q3 No transition so leave it
 Example: Accepting

a a

q1 a q2 Since there is no more

symbol to read and
a it is an accepting state
Therefore, the
NFA will “Accept”
Start
q0
a
q3
 Example: Rejecting

a a a

q1 a q2
a
Start
q0
a
q3
 Example: Rejecting

a a a

q1 a q2
a
Start
q0
a
q3
 Example: Rejecting

a a a

q1 a q2
a
Start
q0
a
q3 No transition
 Example: Rejecting

a a a

q1 a q2 No transition so leave
the state
a
Start
q0 Since there is no current state or
a accepting state therefore, NFA will
“Reject” the input string.
q3
 Language of the NFA

L  {aa}

q1 a q2
a
Start
q0
a
q3
TRANSITION GRAPHS

Relaxed input conditions

Can read multiple characters before making a transition

Thus every edge can be labeled with a substring instead of a single

character

Can have multiple start states

TRANSITION GRAPHS
Examples
 All words that start and end with a double letter

a,b
aa,bb
-1 2

aa,bb
+3
EXAMPLES
The arc from state 1 to state 2 is labeled with the string
aa, which is not a single letter.
There are two arcs leaving state 2 labeled with b.
There is no arc leaving state 2 labeled with a.
There is an arc from state 1 to state 3 labeled with ,
which is not a letter from .
There is no arc leaving state 3 labeled with b.
TRANSITION GRAPHS

Examples
 All words that have al least one double letter in them
 All words that begin and end with different letters
 All words in which a occurs only in even clumps and that end in three or more bs
 All words that have even number of letters
GENERALIZED
TRANSITION
a*
GRAPHS
a*

(ba +a)* (b + Λ)
-1 2 3

This machine accepts all strings without a double b

GTGS

Examples
 All words having even number of as and bs

 All words that start with ab

 All words having as in clumps of even numbers and end at one or more bs