XJCO2321 Formal Languages and

Finite Automata

03: Deterministic Finite Automata

and Regular Languages
 Today’s Objectives
• To introduce State Diagram
• To introduce Deterministic Finite
Automaton (DFA)
• To provide formal definition of DFA

Based on slides by Costas Busch 1

 Deterministic Finite Automaton (DFA)

Input Tape
String
Output
“Accept”
Finite
or
Automaton
“Reject”

Based on slides by Costas Busch 2

 Transition Diagram (Graph)
a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

initial accepting
state state
transition
state
Based on slides by Costas Busch 3
 Alphabet  = {a , b }
a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

For every state, there is a transition

for every symbol in the alphabet

Based on slides by Costas Busch 4

 Initial Configuration
Input Tape
a b b a
Input String
a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

Initial state
Based on slides by Costas Busch 5
 Scanning the Input

a b b a

head a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 6

 a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 7

 a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 8

 Input finished
a b b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4 accept

Last state determines the outcome

Based on slides by Costas Busch 9
 A Rejection Case

a b a
Input String
a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 10

 a b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 11

 a b a

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 12

 Input finished
a b a

a, b

reject
q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

Last state determines the outcome

Based on slides by Costas Busch 13
 Another Rejection Case
Tape is empty

Input Finished (no symbol read)
a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

reject
Based on slides by Costas Busch 14
 This automaton accepts only one string

Language Accepted: L = abba 

a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 15

 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

Based on slides by Costas Busch 16

 Another Example

L =  , ab, abba
a, b

q5
b a a a, b
b
q0 a q1 b q2 b q3 a q4

Accept Accept Accept

state state state
Based on slides by Costas Busch 17
 Empty Tape

Input Finished
a, b

q5
b a a a, b
b
q0 a q1 b q2 b q3 a q4

accept
Based on slides by Costas Busch 18
 Another Example

a a, b

q0 b q1 a, b q2

Accept trap state

state
Based on slides by Costas Busch 19
 a a b
Input String

a a, b

q0 b q1 a, b q2

Based on slides by Costas Busch 20

 a a b

a a, b

q0 b q1 a, b q2

Based on slides by Costas Busch 21

 a a b

a a, b

q0 b q1 a, b q2

Based on slides by Costas Busch 22

 Input finished

a a b

a a, b
accept

q0 b q1 a, b q2

Based on slides by Costas Busch 23

 A rejection case

b a b
Input String

a a, b

q0 b q1 a, b q2

Based on slides by Costas Busch 24

 b a b

a a, b

q0 b q1 a, b q2

Based on slides by Costas Busch 25

 b a b

a a, b

q0 b q1 a, b q2

Based on slides by Costas Busch 26

 Input finished
b a b

a a, b

q0 b q1 a, b q2

reject

Based on slides by Costas Busch 27

 Language Accepted: L = {a b : n  0 }
n

a a, b

q0 b q1 a, b q2

Based on slides by Costas Busch 28

 Another Example
Alphabet:  = {1}
1

q0 q1
1
Language Accepted:

EVEN = {x : x   and x is even}

*

= { , 11, 1111, 111111, }

Based on slides by Costas Busch 29
 Formal Definition

M = (Q, ,  , q0 , F )
Q : set of states
 : input alphabet  
 : transition function
q0 : initial state

F : set of accepting states

Based on slides by Costas Busch 30
 Set of States Q
Example

Q = q0 , q1, q2 , q3 , q4 , q5 
a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 31

 Input Alphabet 

  :the input alphabet never contains 

empty string

Example
 = a, b a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 32

 Initial State q0

Example
a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 33

Set of Accepting States F  Q

Example
F = q4  a, b

q5
a, b
b a a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 34

Transition Function  :Q → Q

 (q , x ) = q 
x
q q

Describes the result of a transition

from state q with symbol x

Based on slides by Costas Busch 35

 Example:
 (q0 , a ) = q1

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 36

  (q0 , b ) = q5

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 37

  (q2 , b ) = q3

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch Costas Busch - LSU 38

38
Transition Table for 
symbols
 a b
q0 q1 q5
q1 q5 q2
states

q2 q5 q3
a, b
q3 q4 q5
q4 q5 q5
q5
q5 q5 q5 a, b
b a a b
q0 a q1 b q2 b q3 a q4
Based on slides by Costas Busch 39
Extended Transition Function
 :Q   → Q
* *

 (q ,w ) = q 
*

Describes the resulting state

after scanning string w from state q

Based on slides by Costas Busch 40

 Example:  (q0 , ab ) = q2
*

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4
Based on slides by Costas Busch 41
  (q0 , abbbaa ) = q5
*

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 42

  (q1 , bba ) = q4
*

a, b

q5
b a a, b
a b
q0 a q1 b q2 b q3 a q4

Based on slides by Costas Busch 43

 Special case:

for any state q

 (q,  ) = q
*

Based on slides by Costas Busch 44

 In general:  (q ,w ) = q 
*

implies that there is a walk of transitions

w =  1 2  k
1 2 k
q q
states may be repeated

q w q
Based on slides by Costas Busch 45
 Language Accepted by DFA

Language accepted by DFA M:

it is denoted as L(M ) and contains
all the strings accepted by M

We also say that M recognizes L(M )

Based on slides by Costas Busch 46

 Language Accepted by DFA

Language accepted by DFA M:

it is denoted as L(M ) and contains
all the strings accepted by M

We also say that M recognizes L(M )

Based on slides by Costas Busch 47

 M


L(M ) = w   :  (q0 , w)  F
* *

q0 w q q  F

Based on slides by Costas Busch 48

 More DFA Examples
 = {a , b }
a, b
a, b

q0 q0

L(M ) = { } L(M ) =  *

Empty language All strings

Based on slides by Costas Busch 49
  = {a , b }

a, b

q0 a, b q1

L( M ) = { }
Language of the empty string
Based on slides by Costas Busch 50
  = {a , b }

L(M ) = { all strings with prefix ab }

a, b

q0 a q1 b q2

b a accept

q3 a, b

Based on slides by Costas Busch 51

 L(M ) = { all binary strings containing
substring 001 }

0,1
1 0
1

 0 0 00 1 001
0

Based on slides by Costas Busch 52

 L(M ) = { all binary strings without
substring 001 }

1 0
0,1
1

 0 1
0 00 001

0
Based on slides by Costas Busch 53
 
L( M ) = awa : w  a, b
*
 a
b
b
q0 a q2 q3

b a
q1

a, b
Based on slides by Costas Busch 54
 Regular Languages
Definition:
A language L is regular if there is
a DFA M that accepts it ( L(M ) = L )

The languages accepted by all DFAs

form the family of regular languages

Based on slides by Costas Busch 55

 Example regular languages:

abba  , ab, abba

{a b : n  0}
n
awa : w  a, b 
*

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

{ all binary strings without substring 001}
{x : x  {1} and x is even}*

{ } { } *
{a, b}
There exist DFAs that accept these
languages (see previous slides).
Based on slides by Costas Busch 56
There exist languages which are not Regular:

L= {a b : n  0}
n n

ADDITION = {x + y = z : x = 1 ,y = 1 ,z = 1 ,
n m k

n + m = k}

There are no DFAs that accept these languages

(we will prove this later)

Based on slides by Costas Busch 57

 Follow-Up / Further Reading
• Read Chapter 1.1 of Sipser

Based on slides by Costas Busch 58