Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    TOC4

    Uploaded by

    Sharmila Devi

    Copyright:

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

    TOC4

    Uploaded by

    Sharmila Devi
    15 views2 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    TOC4

    Uploaded by

    Sharmila Devi

    Copyright:

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

    Code: 19A05501 R19

    B.Tech III Year I Semester (R19) Regular Examinations February 2022


    FORMAL LANGUAGES & AUTOMATA THEORY
    (Computer Science & Engineering)
    Time: 3 hours Max. Marks: 70
    PART – A
    (Compulsory Question)
    *****
    1 Answer the following: (10 X 02 = 20 Marks)
    (a) Define non-deterministic finite automata.
    (b) Draw the digraph for the following: G = ({1, 2, 3, 4, 5, 6}, {i->j|i<j}).
    (c) Define and explain Kleene Closure for regular expression.
    (d) Construct a regular expression for the set of strings in (0+1)* such that any two 0’s are separated by
    a string, whose length is 4i, for some i >=0.
    (e) What is useless symbol in a grammar give an example?
    (f) With example, explain left recursion.
    (g) Give the formal definition of PDA.
    (h) Define two stack PDA.
    (i) Define Church’s thesis.
    (j) Define post correspondence problem.

    PART – B
    (Answer all the questions: 05 X 10 = 50 Marks)

    n(n+1)(2n+1)
    2 (a) Prove that ∑𝑛𝑛𝑖𝑖=0 i2 = .
    6
    (b) Explain the steps to convert NFA to DFA. Illustrate with an example.
    OR
    3 (a) What is Mealy machine? Design Mealy machine for incrementing the value of any binary number
    by one. The output should also be a binary number with value one more than the number given.
    (b) Minimize the following DFA.

    4 (a) Prove that the following language is non-regular:


    L= {anbn | n>0}
    Use Pumping Lemma.
    (b) State and prove Pumping Lemma for regular languages.
    OR
    5 (a) Construct a DFA that accepts the language represented by 0*. 1*. 2*
    (b) Briefly explain any two closure properties of RLs.

    Contd. in page 2

    Page 1 of 2
    Code: 19A05501 R19

    6 Convert the grammar G to Greibach normal form:


    G = ({A1,A2, A3}, {a,b}, P,A)
    Where P consist of:
    A1 ->A2A3
    A2->A3A1|b
    A3->A1A2|a
    OR
    7 (a) Eliminate the unit productions from the following grammar:
    S-> a | Xb | aYa | b | aa
    X-> Y
    Y-> b | X
    (b) Convert the following grammar into CNF:
    E → E+T/T
    T → T∗ F/F
    F → (E)/a/ab/ba

    8 (a) Construct a PDA that accepts the following language L= { an bn n>=0 }. Show the moves of PDA
    for aabb.
    (b) Write about applications of PDA.
    OR
    9 (a) Explain DPDA and NPDA.
    (b) Construct of PDA for recognizing the language generated by the following CFG:
    S → AB│BA
    A → aA│a
    B → bB│b

    10 Explain the following: (i) Composite TM. (ii) Halting problem of TM.
    OR
    11 Explain NP, NP Hard and NP complete problems.

    *****

    Page 2 of 2

    You might also like