Scribd Logo
Upload

Welcome to Scribd!

  • 3 views

    CS292 Ca2

    Uploaded by

    ahwarsi

    Copyright:

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

    CS292 Ca2

    Uploaded by

    ahwarsi
    3 views2 pages

    Original Title

    CS292 CA2

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    CS292 Ca2

    Uploaded by

    ahwarsi

    Copyright:

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

    PROGRAM NAME: B.

    Tech
    YEAR/SEMESTER: II/IV
    COURSE NAME: Theory of Computations
    COURSE CODE: CS292

    Time: 1.30 hrs.


    Max. Marks: 20

    Note:
    (i) The question paper contains Three Sections.
    (ii) Section-A is compulsory. Section-B and C contain internal choice.

    SECTION-A
    (VERY SHORT ANSWER QUESTIONS)
    Attempt ALL parts of the following questions: 0.5 x 10 = 5

    1. What is the Chomsky Hierarchy? [BT-1/2 CO-2 PO-2]


    2. Define a Context-Free Grammar (CFG). [BT-1/2 CO-3 PO-3]
    3. Explain the significance of Deterministic Push Down Automata (PDA). [BT-1/2 CO-4
    PO-4]
    4. Write a regular expression over {0,1} denotes set of all strings not containing 100 as a
    substring. [BT-1/2 CO-2 PO-5]
    5. What is the difference between DFA and NFA? [BT-1/2 CO-2 PO-2]
    6. Define Ambiguity in Grammar. [BT-1/2 CO-3 PO-3]
    7. What is residue modulo 5 in a DFA. [BT-1/2 CO-2 PO-4]
    8. What is the Pumping Lemma for regular languages? [BT-1/2 CO-2 PO-2]
    9. Define Push Down Automata (PDA). [BT-1/2 CO-4 PO-5]
    10. What is reverse loop. [BT-1/2 CO-3 PO-4]

    SECTION-B
    (SHORT ANSWER QUESTIONS)
    Attempt any TWO of the following questions: 2.5 x 2 = 5

    1. Discuss the process of converting a Nondeterministic Finite Automata (NFA) to


    Deterministic Finite Automata (DFA). [BT-3/4 CO-2 PO-3]
    2. Describe in detail the Simplification of CFGs and its importance. [BT-3/4 CO-3 PO-4]
    3. Prove Arden’s Theorem with an example. [BT-3/4 CO-2 PO-5]
    4. Construct a grammar for a set of all strings whose starting and ending symbols are
    different. [BT-3/4 CO-3 PO-2]

    SECTION-C
    (LONG ANSWER QUESTIONS)
    Attempt any TWO of the following questions: 5 x 2 = 10
    1. Analyze the relationship between Context-Free Languages (CFL) and Push Down
    Automata (PDA), including the equivalence between PDA and CFG. Provide examples.
    [BT-4/5/6 CO-3 PO-3]
    2. Given a grammar [S-> XX
    X->XXX/Bx/Xb/a],
    Substring = bbaaaab,
    Consider the substring and draw its parched tree [BT-4/5/6 CO-3 PO-5]

    3. Find the regular expression of the following using Arden’s Theorem . [BT-4/5/6 CO-2
    PO-2]

    4. Consider the CFG and remove the unit production [BT-4/5/6 CO-3 PO-2]
    S->AB
    A->a
    B->C/b
    C->D
    D->E
    E->a

    You might also like