Scribd Logo
Upload

Welcome to Scribd!

  • 12 views

    Eurcs Eurit 505

    Uploaded by

    Durga K
    The document describes an exam for a formal languages and automata theory course. It covers topics like finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, and the Post's correspondence problem. The exam contains 5 units and 10 questions, and students must answer one question from each unit.

    Copyright:

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

    Eurcs Eurit 505

    Uploaded by

    Durga K
    12 views4 pages
    The document describes an exam for a formal languages and automata theory course. It covers topics like finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, and the Post's correspondence problem. The exam contains 5 units and 10 questions, and students must answer one question from each unit.

    Original Title

    EURCS-EURIT-505

    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 describes an exam for a formal languages and automata theory course. It covers topics like finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, and the Post's correspondence problem. The exam contains 5 units and 10 questions, and students must answer one question from each unit.

    Copyright:

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

    Eurcs Eurit 505

    Uploaded by

    Durga K
    The document describes an exam for a formal languages and automata theory course. It covers topics like finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, and the Post's correspondence problem. The exam contains 5 units and 10 questions, and students must answer one question from each unit.

    Copyright:

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

    [EURCS 505/EURIT 505]

    B.Tech. DEGREE EXAMINATION


    CSE/IT
    V SEMESTER
    FORMAL LANGUAGES & AUTOMATA THEORY
    (Effective from the admitted batch 2007–08)
    Time: 3 Hours Max.Marks: 60
    -----------------------------------------------------------------------------------
    Instructions: Each Unit carries 12 marks.
    Answer all units choosing one question from each unit.
    All parts of the unit must be answered in one place only.
    Figures in the right hand margin indicate marks allotted.
    -----------------------------------------------------------------------------------
    UNIT-I
    1. a) Compare Deterministic and Non-Deterministic Finite Automata.
    6
    b) Construct deterministic finite Automata to recognize
    the following.
    i) Strings of binary ending with the pattern ‘101’
    ii) Strings of binary with even length. 6
    OR
    2. a) Explain the procedure for converting a given DFA to
    regular Expression. 6
    b) Convert the following regular expression to NFA with
    E-moves.
    (00+10+01)*. 6
    UNIT-II
    3. a) State and explain the pumping Lemma for regular sets 6
    b) Check whether the following are regular sets
    i) L= a n b n | n 0
    ii) L= x | x (0 1)* and has equal no of zeros and ones 6
    OR
    4. a) Explain the theorem for checking emptiness, finiteness
    and infiniteness of regular Languages. 6
    b) What are indistinguishable states in a finite Automata.
    Explain the algorithm for minimization of finite Automata. 6
    UNIT-III
    5. a) Check if the following context free grammar is Ambiguous.
    E → E+E
    E → E*E
    E → id 6
    b) Explain the steps involved in eliminating useless symbols in
    a given context free Grammar 6
    OR
    6. a) State and explain the closure properties of Context Free
    Languages. 6
    b) Convert the following CFG to Greibach Normal form.
    S → AA
    A → AAA
    A→a
    A → bA
    A → Ab 6
    UNIT-IV
    7. a) Give the formal Definition of a Push Down Automata. 6
    b) Construct Push Down Automata to recognize the language
    of equal number of a’s and b’s. 6
    OR
    8. a) Explain the construction steps involved in converting a
    given Push Down Automata to Context Free Language. 6
    b) Check whether the following Language is LR(K) grammar
    S → (A)
    S→a
    A → SA
    A→e 6
    UNIT-V
    9. What is a Turning Machine. Construct a Turing machine to
    compute proper subtraction of two positive integers. Proper
    Subtraction of two integers ‘a’ and ‘b’ is a-b if a > b and 0
    otherwise 12
    OR
    10. What are undecidable problems. Check whether the following
    instance of Posts Correspondence problem (PCP) has a solution
    or not. 12
    i xi wi
    1 b ca
    2 a ab
    3 ca a
    4 abc c

    [3,7/VS/109]

    You might also like