Scribd Logo
Upload

Welcome to Scribd!

  • 8 views

    TC - August - 2015

    Uploaded by

    NALE SVPMEngg
    The document is a test paper containing 6 questions about theory of computation. It includes questions on deterministic finite automata, regular expressions, context free grammars, Chomsky normal form, and the Chomsky hierarchy.

    Copyright:

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

    TC - August - 2015

    Uploaded by

    NALE SVPMEngg
    8 views3 pages
    The document is a test paper containing 6 questions about theory of computation. It includes questions on deterministic finite automata, regular expressions, context free grammars, Chomsky normal form, and the Chomsky hierarchy.

    Original Description:

    Theory Of Computation Question Paper

    Original Title

    TC_ August_2015

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document is a test paper containing 6 questions about theory of computation. It includes questions on deterministic finite automata, regular expressions, context free grammars, Chomsky normal form, and the Chomsky hierarchy.

    Copyright:

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

    TC - August - 2015

    Uploaded by

    NALE SVPMEngg
    The document is a test paper containing 6 questions about theory of computation. It includes questions on deterministic finite automata, regular expressions, context free grammars, Chomsky normal form, and the Chomsky hierarchy.

    Copyright:

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

    Total No. of Questions : 6] SEAT No.

    :
    P4880 [Total No. of Pages : 3

    T.E./Insem. - 152
    T.E. (IT)
    THEORY OF COMPUTATION
    (2012 Pattern) (Semester - I)
    Time : 1 Hour] [Max. Marks : 30
    Instructions to the candidates :
    1) Answer Q1 or Q2, Q3 or Q4, Q5 or Q6.
    2) Neat diagrams must be drawn wherever necessary.
    3) Figures to the right indicate full marks.
    4) Assume suitable data, if necessary.

    Q1) a) Construct a deterministic finite automata (DFA) that recognizes the


    language L= {x∈ (0,1) | (x contains atleast two consecutive 0’s) and
    (x does not contain two consecutive 1’s)} [4]
    b) Convert the given NFA–ε to an NFA. [6]

    OR
    Q2) a) Minimize the following automata. [6]

    b) Convert following Moore machine into Mealy Machine. [4]

    P.T.O.
    Next State
    Present State a = 0 a = 1 Output
    -> q0 q3 q1 1
    q1 q2 q3 0
    q2 q2 q1 0
    q3 q1 q0 1

    Q3) a) Find the regular expression corresponding to each of the following subset
    of {0, 1} [4]
    i) Language of all Strings not containing the substring 000.
    ii) Language of all Strings containing an even no of 0’s.
    b) Show that L={anb2n | n>0} is not regular. [6]
    OR
    Q4) a) Construct a regular expression for given finite automata. [6]

    b) Convert Right Linear Grammar to equivalent Left Linear grammar [4]


    S->bB
    B->bC
    B->aB
    C->a
    B->b

    Q5) a) Convert the following grammar in Chomsky NF [8]


    S→01XY
    X→1XY | ∈
    Y→YX0 |X| ∈
    b) Define Context free Grammar with example. [2]

    Insem. - 152 2
    OR
    Q6) a) Write a context free grammar for following Language [6]
    i) L= {ambncp | m+n=p}
    ii) (a+b)b(a+b)*b(a+b)
    b) Write short note on Chomsky Hierarchy. [4]

    ïïï

    Insem. - 152 3

    You might also like