1 of 41

Session 3 and 4: �Finite State systems – Deterministic Finite Automaton – DFA

By

Dr. Ashok Kumar

Amity School of Engineering & Technology

2 of 41

Automaton

CPU

input memory

output memory

Program memory

temporary memory

Automaton

Amity School of Engineering & Technology

3 of 41

CPU

input memory

output memory

Program memory

temporary memory

compute

compute

Amity School of Engineering & Technology

4 of 41

Different Kinds of Automata

Automata are distinguished by the temporary memory

​

    • Finite Automata: no temporary memory

​

    • Pushdown Automata: stack (LIFO)

​

    • Turing Machines: random access memory

Amity School of Engineering & Technology

5 of 41

input memory

output memory

temporary memory

Finite

Automaton

Finite Automaton

Example: Vending Machines

(small computing power)

Amity School of Engineering & Technology

6 of 41

input memory

output memory

Stack

Pushdown

Automaton

Pushdown Automaton

Example: Compilers for Programming Languages

(medium computing power)

Push, Pop

Amity School of Engineering & Technology

7 of 41

input memory

output memory

Random Access Memory

Turing

Machine

Turing Machine

Examples: Any Algorithm

(highest computing power)

Amity School of Engineering & Technology

8 of 41

Finite

Automata

Pushdown

Automata

Turing

Machine

Power of Automata

Less power

More power

Solve more

computational problems

Amity School of Engineering & Technology

9 of 41

Finite State systems – Basic Definitions – Finite Automaton – DFA & NDFA

Amity School of Engineering & Technology

10 of 41

Formal Definition

10

Deterministic Finite Accepter (DFA)

: set of states

: input alphabet

: transition function

: initial state

: set of final states

Amity School of Engineering & Technology

11 of 41

Input Alphabet

11

Amity School of Engineering & Technology

12 of 41

Set of States

12

Amity School of Engineering & Technology

13 of 41

Initial State

13

Amity School of Engineering & Technology

14 of 41

Set of Final States

14

Amity School of Engineering & Technology

15 of 41

Transition Function

15

Amity School of Engineering & Technology

16 of 41

16

Amity School of Engineering & Technology

17 of 41

17

Amity School of Engineering & Technology

18 of 41

18

Amity School of Engineering & Technology

19 of 41

Transition Function

19

Amity School of Engineering & Technology

20 of 41

Extended Transition Function

20

Amity School of Engineering & Technology

21 of 41

21

Amity School of Engineering & Technology

22 of 41

22

Amity School of Engineering & Technology

23 of 41

23

Amity School of Engineering & Technology

24 of 41

24

 Observation:  There is a walk from      to      with label

Amity School of Engineering & Technology

25 of 41

25

 Example:  There is a walk from       to       with label

Amity School of Engineering & Technology

26 of 41

Languages Accepted by DFAs

  • Take DFA

​

  • Definition:
    • The language              contains 
    • all input strings accepted by 

​

​

    •                   = { strings that drive       to a final state}   

26

Amity School of Engineering & Technology

27 of 41

Example

27

accept

Amity School of Engineering & Technology

28 of 41

Another Example

28

accept

accept

accept

Amity School of Engineering & Technology

29 of 41

Formally

​

  • For a DFA

​

  • Language accepted by       :

​

​

​

29

Amity School of Engineering & Technology

30 of 41

Observation

  • Language rejected by      :

30

Amity School of Engineering & Technology

31 of 41

Examples

Amity School of Engineering & Technology

32 of 41

Examples

Amity School of Engineering & Technology

33 of 41

Examples

Amity School of Engineering & Technology

34 of 41

Examples

Amity School of Engineering & Technology

35 of 41

Examples

Amity School of Engineering & Technology

36 of 41

More Examples

36

Design a DFA that accepts the following Language:

Amity School of Engineering & Technology

37 of 41

accept

trap state

Amity School of Engineering & Technology

38 of 41

38

Design a DFA which accepts the following language.

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

Amity School of Engineering & Technology

39 of 41

Regular Languages

​

  • A language L is regular if there is a DFA  M   such that L = L(M)
  • All regular languages form a language family

39

Amity School of Engineering & Technology

40 of 41

Example

  • The language L = {awa : w ∈ {a, b}* is regular:

​

​

40

Amity School of Engineering & Technology

41 of 41

41

There exist languages which are not Regular:

There is no DFA that accepts such a language

(we will prove this later in the class)

Example:

Amity School of Engineering & Technology