Home QBASIC C Java HTML
  • More Courses
  • MCQs
  • Blog Download
  • Tools
  • Contact

    Automata theory (Discrete Structure Note Introduction)

    Posted on 2021-03-27

    The Term "Automata" is derived from the Greek word "αὐτόματα" which means "self-acting". in general, Automata is an abstract computing device that follows a predetermined sequence of operations automatically. 

    Thus Automata is a special kind of machine that is closely linked to a particular type of language. In this chapter, we will discuss finite-state automata and their languages. 

    Sequential Circuits and Finite State Machine

     

    Alphabet 

    An alphabet is any finite set of symbols. 

    Example: S={a, b, c, d} is an alphabet set where 'a', 'b', 'c', and 'd' are symbols. 

     

    String

    A string is a finite set of symbols taken from S. 

    Example: 'cabcad' is a string on the alphabe set S={a,b,c,d}

     

    Length of String 

    Length of string is the number of symbols present in a string. (Denoted by |s|. 

    Example: 

    • If S='cabcad', |s|=6
    • If |S| = 0, it is called an empty string Denoted by λ or ε

     

    Finite State Automata 

    FAS is a simple model of computation. It has very limited memory. FSA can be classified into two broad categories: DFA and NFA. 

    DFA = Deterministic Finite Automata 
    NFA = Non-deterministic Finite Automata
     
     
    What is DFA?
    DFA is deterministic finite automata. It has the following features. 
    1. Given the current state, we will know what the next state will be 
    2. It has only one unique next state
    3. It has no choices or randomness
    4. It is simple and easy to design

    A deterministic finite-state machine is an abstract model with a primitive internal memory with four basic components.

         Q: set of all state
         Σ: inputs
         δ: transition function from Q × Σ
         q0 : start state / initial states

    Graphical representation of DFA

    A DFA is represented by digraphs called state diagrams. in a state diagram

    • The verities represent the states.
    • The arcs labeled with an input alphabet show the transitions. 
    • The initial state is denoted by an empty single incoming arrow. 
    • The finite state is indicated by double circles. 

     


    177