Deterministic Finite

Automata
  Deterministic Finite Automata (DFA)
Finite  The machine can exist in only one state at any given time

Automata  Non-deterministic Finite Automata (NFA)

 The machine can exist in multiple states at the same time
  In automata theory, a finite-state machine is called a deterministic
finite automaton (DFA), if
 each of its transitions is uniquely determined by its source state
and input symbol, and

Deterministic  reading an input symbol is required for each state transition

 epsilon is excluded (ε)
Finite
Automata
(DFA)
  A nondeterministic finite automaton (NFA), or nondeterministic
finite-state machine, does not need to obey these restrictions.

Non-
deterministic
Finite
Automata
(NFA)
  A Deterministic Finite Automaton (DFA) consists of:
 Q ==> a finite set of states
 ∑ ==> a finite set of input symbols (alphabet)
Deterministic  q0 ==> a start state

Finite  F ==> set of final states

 δ ==> a transition function, which is a mapping
Automata - between Q x ∑ ==> Q
Definition

 A DFA is defined by the 5-tuple:

 {Q, ∑ , q0,F, δ }

5
  Input: a word w in ∑*
 Question: Is w acceptable by the DFA?
 Steps:
What does a  Start at the “start state” q0
DFA do on  For every input symbol in the sequence w do
 Compute the next state from the current state, given the
reading an current input symbol in w and the transition function
input string?  If after all symbols in w are consumed, the current
state is one of the final states (F) then accept w;
 Otherwise, reject w.

6
  Let L(A) be a language recognized by a DFA A.
 Then L(A) is called a “Regular Language”.

 What is the position of regular languages in the Chomsky

Hierarchy

Regular  Example of Language:

Languages The language accepting strings starting with ‘a’ over input
alphabets ∑ = {a, b}

 The language accepted by finite automata can be easily described

by simple expressions called Regular Expressions. It is the most
effective way to represent any language.

7
  As discussed in Chomsky Hierarchy, Regular Languages are the most
restricted types of languages and are accepted by finite automata.
 Regular Expressions are used to denote regular languages.

Regular  L(01) = {01}.

 L(01+0) = {01, 0}.
Expressions
 L(0(1+0)) = {01, 00}.
 Note order of precedence of operators.

 L(0*) = {ε, 0, 00, 000,… }.

 L()= { 10,100,1000,10000,…..}

 L((0+10)*(ε+1)) = all strings of 0’s and 1’s without two consecutive 1’s.
Regular
Expressions
 • What makes this DFA deterministic?

• Q = {q0,q1,q2}
1 0 0,1 • ∑ = {0,1}
DFA for strings • start state = q0
1
containing 01 start q0 0 q1 q2 • F = {q2}
Final • Transition table
state symbols
0 1
q0 q1 q0

states
q1 q1 q2
*q2 q2 q2

10
  Determine the minimum substring according to the Language condition
and draw possible states.
 Decide the strings for which DFA will be constructed.
 Construct a DFA for the strings decided in Step-02.
Steps for DFA
construction

 Send all the left possible combinations to the dead state.

 • We don't draw multiple arrows with the same source and destination states:

A DFA
Convention • Instead, we draw one arrow with a list of symbols:

12
  Draw a DFA for the language accepting strings starting with ‘ab’ over input
alphabets ∑ = {a, b}

 Step-01:
 All strings of the language starts with substring “ab”.
 So, minimum condition will have 3 states for reading substring ab

DFA Examples
 Step-02:
 We will construct DFA for the R.E ab(a+b)*
 ab
 aba
 abb
 abab
 Step 3

DFA
Step 4
 1. Draw a DFA for the language accepting strings starting with ‘a’ over input
alphabets ∑ = {a, b}

2. Design a DFA with ∑ = {0, 1} that accepts those strings which starts with 1 and
ends with 0.

3. Design a DFA with ∑ = {0, 1} that accepts even number of 0's and even number of
Examples 1's.

4. Draw a DFA for the language accepting strings starting with ‘101’ over input
alphabets ∑ = {0, 1}

5. Design a DFA that accepts only two words baa & ab

6. Design a DFA that accepts all words with triple letters either aaa or bbb over input
alphabets ∑ = {a, b}

7. Design a DFA that accepts all words that have different first and last letters. If the
word begins with an ‘a’ then it must ends with a ‘b’ and vice versa.
 • A man must cross river with wolf, goat and
cabbage

• Has rowboat w/ room for man plus one

possession
A Classic Riddle • If left alone together:
• Wolf eats goat
• Goat eats cabbage

How can the man cross without loss?

 • Four moves can be encoded as four symbols:
– Man crosses with wolf (w)
– Man crosses with goat (g)
– Man crosses with cabbage (c)
Solutions As – Man crosses with nothing (n)

Strings • Then sequence of moves is a string, such as

gnwgcng:
– First cross with goat, then cross back with nothing,
then cross with wolf, …

17
 • Each move takes our puzzle universe from one state to
another
• For example, the g move is a transition
Moves As State between these two states:
Transitions

18
 • Showing all legal moves
• All reachable states
Transition • Start state and goal state
Diagram

19