Scribd Logo
Upload

Welcome to Scribd!

  • 72 views

    Theory of Computation (CS F351) : BITS Pilani

    Uploaded by

    avi
    This document discusses non-deterministic finite automata (NDFA) and their relationship to deterministic finite automata (DFA). It defines what an NDFA is and notes that while NDFA are not meant to model computers realistically, they allow for simpler descriptions of languages. It also explains that every NDFA can be converted to an equivalent DFA using algorithms described in the document.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Theory of Computation (CS F351) : BITS Pilani

    Uploaded by

    avi
    72 views15 pages
    This document discusses non-deterministic finite automata (NDFA) and their relationship to deterministic finite automata (DFA). It defines what an NDFA is and notes that while NDFA are not meant to model computers realistically, they allow for simpler descriptions of languages. It also explains that every NDFA can be converted to an equivalent DFA using algorithms described in the document.

    Original Title

    toc4.1.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses non-deterministic finite automata (NDFA) and their relationship to deterministic finite automata (DFA). It defines what an NDFA is and notes that while NDFA are not meant to model computers realistically, they allow for simpler descriptions of languages. It also explains that every NDFA can be converted to an equivalent DFA using algorithms described in the document.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    72 views15 pages

    Theory of Computation (CS F351) : BITS Pilani

    Uploaded by

    avi
    This document discusses non-deterministic finite automata (NDFA) and their relationship to deterministic finite automata (DFA). It defines what an NDFA is and notes that while NDFA are not meant to model computers realistically, they allow for simpler descriptions of languages. It also explains that every NDFA can be converted to an equivalent DFA using algorithms described in the document.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 15

    Theory of Computation (CS F351)

    Prof.R.Gururaj
    BITS Pilani CS&IS Dept.
    Hyderabad Campus
    Non-deterministic
    Finite Automata (Sec. 2.2 of T1)
    Prof.R.Gururaj
    BITS Pilani CS&IS Dept.
    Hyderabad Campus
    What is non-determinism in FA?

    It is a powerful feature.

    What is this nondeterminism?

    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus


    A Deterministic Finite Automaton (DFA)

    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus


    A Non-deterministic Finite Automaton (NDFA) for the same language

    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus


    NDFA for the same language with null transition

    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus


    Description of an NDFA

    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus


    About NDFA

     NDFA are not meant as realistic models for computers.

     They simply notational generalization of FA, as they simplify


    the description of these FA.

     Meaning that we can draw a FA for a language with ease


    (less number of states and edges)

     Further, non-determinism is a non-essential feature of FA.

     Ever NDFA can be converted to equivalent DFA.

     We have algorithms that can convert NDFA to its equivalent


    DFA.
    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus
    Converting a NDFA without
    null moves, to equivalent DFA

    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus


    Converting a NDFA without
    null moves, to equivalent DFA

    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus


    Converting a NDFA with null
    moves, to equivalent DFA

    Ex.1

    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus


    Computing E(q) for each qϵK

    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus


    Defining the transitions of DFA

    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus


    Final equivalent DFA

    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus


    Converting a NDFA with null
    moves, to equivalent DFA

    Prof.R.Gururaj CSF351 Theory of Computation BITS Pilani, Hyderabad Campus

    You might also like