Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    Uti

    Uploaded by

    courageouscse
    1. A finite automaton is a mathematical model that consists of a finite set of states and transitions between states depending on input symbols. 2. A deductive proof is a sequence of statements that starts from a hypothesis and uses logical principles to reach a conclusion. 3. Proof by contrapositive proves a statement "If P then Q" by proving its contrapositive "If not Q then not P". 4. An induction proof shows a statement S(n) is true for all integers n by showing S(1) is true and if S(k) is true then S(k+1) is also true.

    Copyright:

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

    Uti

    Uploaded by

    courageouscse
    15 views2 pages
    1. A finite automaton is a mathematical model that consists of a finite set of states and transitions between states depending on input symbols. 2. A deductive proof is a sequence of statements that starts from a hypothesis and uses logical principles to reach a conclusion. 3. Proof by contrapositive proves a statement "If P then Q" by proving its contrapositive "If not Q then not P". 4. An induction proof shows a statement S(n) is true for all integers n by showing S(1) is true and if S(k) is true then S(k+1) is also true.

    Original Description:

    Finite Automata

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. A finite automaton is a mathematical model that consists of a finite set of states and transitions between states depending on input symbols. 2. A deductive proof is a sequence of statements that starts from a hypothesis and uses logical principles to reach a conclusion. 3. Proof by contrapositive proves a statement "If P then Q" by proving its contrapositive "If not Q then not P". 4. An induction proof shows a statement S(n) is true for all integers n by showing S(1) is true and if S(k) is true then S(k+1) is also true.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    15 views2 pages

    Uti

    Uploaded by

    courageouscse
    1. A finite automaton is a mathematical model that consists of a finite set of states and transitions between states depending on input symbols. 2. A deductive proof is a sequence of statements that starts from a hypothesis and uses logical principles to reach a conclusion. 3. Proof by contrapositive proves a statement "If P then Q" by proving its contrapositive "If not Q then not P". 4. An induction proof shows a statement S(n) is true for all integers n by showing S(1) is true and if S(k) is true then S(k+1) is also true.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 2

    UNIT I

    AUTOMATA
    PART A

    1.What is Finite Automata?


    The finite automaton is a mathematical model of a system with discrete
    inputs and outputs. It consists of a finite set of states and a set of transitions from
    state to state that depends on output symbols.
    2.What is deductive proof? .
    A deductive proof consists of a sequence of statements which starts from a
    hypothesis or a given statement to a conclusion. Each step is satisfying some
    logical principal
    3.Define proof by contra positive.
    It is the other form of If then statement. The contra positive of the
    statement If H then C is If not C then not H
    4.Define induction principle.
    If S(i) is true for n = i ,then it is to be proved that for all n > i , S(n) implies
    S(n+1) then S(n) is true for all n i..
    5.Define NFA.
    It is a five tuple (, Q, , q0, F ) ,where is a finite set of input alphabets, Q is a
    finite set of states, q0 is the initial state, F Q is a set of final states. : Q 2Q is
    a transition function.
    6.List any four ways of theorem proving.
    (i)deductive proof , (ii) contra positive , (iii)Induction principle , (iv) method of
    contradiction.
    7.How a Non deterministic finite state automaton (NFA) differs from a
    Deterministic finite state automaton (DFA).
    Solution:
    DFA
    NFA
    Each symbol causes a move
    The machine can move without consuming
    any symbol and sometimes there is no
    possible move, sometime there are more
    than one possible move
    Next state is completed by The state is only partially determined by
    determining current state and the current state and current input symbol
    current symbol
    The transition function returns only The transition function returns zero, one or

    :Q X Q

    : Q X 2Q

    one state.(i.e)
    more states.(i.e)
    8.Define the languages described by DFA and NFA.
    L(DFA) = { w / (q0,w) is in F}.It is the set of strings w that take the start state
    q0 to one of the accepting states.
    L(NFA)= { w / (q0,w)F}.It is the set of strings w such that (q 0,w)contains
    at least one accepting state.
    9.Define extended transition function for a DFA.
    The extended transition function : Q* Q is defined as follows.(i) (q, ) =
    q (ii)For any w* ,
    a and qQ , (q, wa)= ( (q, w),a)
    10.Define - closure of a state.
    The set of all states reachable from a given state q using transitions only.
    We use -closure to denote the set of all vertices p such that there is a path from
    q to p labeled .
    11.Find the - closure of states 1, 2 and 4 in the following transition
    diagram.
    1-
    2

    b
    4
    5
    a
    b
    7

    S2
    - closure(1) = {1,2,4,3,6},- closure(2) = {2,3,6},closure(4) = {4}.
    1

    S2

    12.Find the set of strings accepted by the finite automata.

    0
    S0

    1
    1

    S1

    S2

    0
    0,1

    S3

    1
    S0

    S1

    S2

    a
    b

    a, b
    a

    a, b

    You might also like