Definition of DFA

Definition of Deterministic Finite Automata

A Deterministic Finite Automaton (DFA) consists of a finite set of states and a set of transitions from one state to another state on input symbols selected from an alphabet S. 

The initial state is generally denoted by q0. 

For each input symbol there is one transition for each state. 

There are one or more “final” or “accepting” states.

The term “deterministic” says that for each input symbol, there is one and only one state to which the automaton can transit from its current state.

In case of “non-deterministic” FA the machine can make transit to zero or one or more states on the same input symbol.

A finite automaton is formally defined by a 5-tuple (Q, Σ, δ, q0, F), 

where, 

Q → Finite set of states. 

Σ → Finite set of input symbols. 

δ → Transition function mapping Q × Σ to Q.  

q0 → Initial state and q0 ∈ Q. 

F → Set of final state/states. It is assumed that there may be more than one final state. F ⊆ Q.

The finite automation has a input tape divided into units, each containing one symbol of the input string which is built from symbols of alphabet Σ. 

The start of tape is indicated by '#' and end is indicated by '$'. 


The tape may be finite or infinite. 

In case of infinite tape, the tape end marker is absent. 

The input string to be processed is stored from left to right direction.

The reading head examines one unit at a time and can move one unit in only one direction generally, left to right. 

The current state ‘q’ and input symbol read by reading head are given as input to the finite control unit. 

The machine may remain in the same state q or transit to a new state and the reading head moves one unit ahead to read the next input symbol. 

This transition is denoted as: δ(qi, a) → qj

Check this video lecture on DFA


Recommended:

  1. Definition of DFA
  2. DFA notations
  3. How DFA process inputs
  4. DFA solved examples
  5. Definition of NFA
  6. Moore machine
  7. Mealy machine
  8. Regular expression examples

Python Programming ↓ 👆
Java Programming ↓ 👆
JAVA EasyExamNotes.com covered following topics in these notes.
JAVA Programs
Principles of Programming Languages ↓ 👆
Principles of Programming Languages
EasyExamNotes.com covered following topics in these notes.

Practicals:
Previous years solved papers:
A list of Video lectures References:
  1. Sebesta,”Concept of programming Language”, Pearson Edu 
  2. Louden, “Programming Languages: Principles & Practices” , Cengage Learning 
  3. Tucker, “Programming Languages: Principles and paradigms “, Tata McGraw –Hill. 
  4. E Horowitz, "Programming Languages", 2nd Edition, Addison Wesley

    Computer Organization and Architecture ↓ 👆

    Computer Organization and Architecture 

    EasyExamNotes.com covered following topics in these notes.

    1. Structure of desktop computers
    2. Logic gates
    3. Register organization
    4. Bus structure
    5. Addressing modes
    6. Register transfer language
    7. Direct mapping numericals
    8. Register in Assembly Language Programming
    9. Arrays in Assembly Language Programming

    References:

    1. William stalling ,“Computer Architecture and Organization” PHI
    2. Morris Mano , “Computer System Organization ”PHI

    Computer Network ↓ 👆
    Computer Network

    EasyExamNotes.com covered following topics in these notes.
    1. Data Link Layer
    2. Framing
    3. Byte count framing method
    4. Flag bytes with byte stuffing framing method
    5. Flag bits with bit stuffing framing method
    6. Physical layer coding violations framing method
    7. Error control in data link layer
    8. Stop and Wait scheme
    9. Sliding Window Protocol
    10. One bit sliding window protocol
    11. A protocol Using Go-Back-N
    12. Selective repeat protocol
    13. Application layer
    References:
    1. Andrew S. Tanenbaum, David J. Wetherall, “Computer Networks” Pearson Education.
    2. Douglas E Comer, “Internetworking with TCP/IP Principles, Protocols, And Architecture",Pearson Education
    3. KavehPahlavan, Prashant Krishnamurthy, “Networking Fundamentals”, Wiley Publication.
    4. Ying-Dar Lin, Ren-Hung Hwang, Fred Baker, “Computer Networks: An Open Source Approach”, McGraw Hill.