Scribd Logo
Upload

Welcome to Scribd!

  • 35 views

    Theory Computation Sep Oct 2022

    Uploaded by

    Keerthana
    This document contains questions from four sections about theory of computation. Some of the key topics covered include: 1. Definitions and representations of finite automata, regular expressions, grammars, and pushdown automata. 2. Converting between representations like regular expressions to grammars or finite automata. 3. Properties of languages and models of computation like closure properties, pumping lemmas, and types of grammars. 4. Designing computational models like finite automata, grammars, and pushdown automata to recognize specific formal languages.

    Copyright:

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

    Theory Computation Sep Oct 2022

    Uploaded by

    Keerthana
    35 views4 pages
    This document contains questions from four sections about theory of computation. Some of the key topics covered include: 1. Definitions and representations of finite automata, regular expressions, grammars, and pushdown automata. 2. Converting between representations like regular expressions to grammars or finite automata. 3. Properties of languages and models of computation like closure properties, pumping lemmas, and types of grammars. 4. Designing computational models like finite automata, grammars, and pushdown automata to recognize specific formal languages.

    Original Description:

    Toc management

    Original Title

    23601TheoryComputationSepOct2022

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains questions from four sections about theory of computation. Some of the key topics covered include: 1. Definitions and representations of finite automata, regular expressions, grammars, and pushdown automata. 2. Converting between representations like regular expressions to grammars or finite automata. 3. Properties of languages and models of computation like closure properties, pumping lemmas, and types of grammars. 4. Designing computational models like finite automata, grammars, and pushdown automata to recognize specific formal languages.

    Copyright:

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

    Theory Computation Sep Oct 2022

    Uploaded by

    Keerthana
    This document contains questions from four sections about theory of computation. Some of the key topics covered include: 1. Definitions and representations of finite automata, regular expressions, grammars, and pushdown automata. 2. Converting between representations like regular expressions to grammars or finite automata. 3. Properties of languages and models of computation like closure properties, pumping lemmas, and types of grammars. 4. Designing computational models like finite automata, grammars, and pushdown automata to recognize specific formal languages.

    Copyright:

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

    --T--

    Ililll ilililllltilil ililtililllil uG - 420


    Vl Semester B. C. A. g*arn i n3t,3, on, Septe m ber/October 2022
    (CBCS) (F+R) (2016-17 and Onwards)
    COMPUTER SCIENCE
    BCA 601 : Theory of Computation
    Time : 3 Hours Max. Marks : 100

    lnstruction : Answer all Sections.

    ECTION _ A

    Answer any ten questions. Each question carries two marks. (10x2=20)

    1. Define finite automata. Give the mathematical representation of finite


    automata.

    2. Find the E-closure of all states for the given E-NFA.

    b,E

    3. Define Kleen closure with an example.


    i

    4. Construct a repular expression for the hnguage consisting of all strings of a's
    and b's beginning with 'a'and ending with 'ab'.

    5. Define left most derivation with an example.

    o. Obtain a grammar to generate the set of all strings wlth exactly one a, over
    I
    = {a, b}.

    7. What is an unit production ?

    P.T.O"
    uG - 420 I ilil fliltil tilt lltil il]t tilt ilil

    8. Draw a parse tree for the following string w = id + id * id having production


    rules
    E-+E+E
    E-+E*E
    E-+id
    Where V = {E}, 1 = {id}, S = {E}.

    9. Define push down automata.

    10. Explain lD (lnstantaneous Description) of turing machine.

    11. Define post correspondence problem.

    2*.
    t
    12. Write the meaning of the regular expression 0* 1*

    . $ECTION -B
    -Answer any five questions. Each question carries marks.
    s (5x5=25)

    13. Check whether the strings "a a bab" and "baba" are accepted by the following
    DFA (Deterministic Finite Automata).
    b

    14. Design a DFA that accepts stringl of a's and b's having a substring ,,aa,,.

    15. Differentiate between DFA, NFA and E-NFA.

    16. Construct an E-NFA for (0x0) + (1*0).

    17. Design a grammar to generate the language L = lanbnln > 0, m > n).
    ItIIlIillilililililillfllililrfl uG - 420
    18. Eliminate the useless symbols in the follow-ing grammar :

    S-+AB
    A-+a
    B -+ blC
    E-+d
    19. Explain the types of turing machines.
    20. Construct the PDA for the grammar S -+ aSbbla.
    (PDA : Push Down'Automata).

    SECTION _ C

    Answer any three questions. Each question carries 1S markl. (15x3=45)

    21. Construct a DFA for the regular expression (alb) x abb. 15

    22. Find a DFA equivalent to the following NFA N = ({go, q1, q2}, {a, b}, 6,q0,{qe})
    where 6 is defined as

    *Qo [Qo, Q,] {or}


    q1 {oo} {0,}
    *Qe {Qo, Q.,}

    DFA : Deterministic Finite Automata I

    NFA : Non-detern{tnistic Finite Automata. 15

    23. a) Verify if the fotlowing grammar is ambiguous. 7


    S -+ aBlbA
    A -+ aSlbAAla
    B -+ bSlaBBlb
    b) Remove E-productions from the following CFG (Context Free Grammar). I
    S -+ XYX
    X -+ OXIE
    Y + lXlE
    uG - 420 Illlllilililt]tlfltililttiltlllt

    24- a) obtain a TMto accept a string w of a,s and b's such that
    u(w) is equal
    N
    to Nb(w).
    7
    (TM : Turing Machine)
    b) state and prove pumping remma for regurar language. I
    25. convert the given grammar to chomsky Normal Form (cNF).
    15
    S + ABICA
    B -+ BCIAB
    A+a
    C -+ aBlb

    SECTION _ D I

    Answer any one of the foilowing questions. Each carries 10 marks. (1x10=10)
    26. Minimize the following Deterministic Finite Automata (DFA).
    10

    27. construct a puftn Down Automata (pDA) to accept the language


    10
    L(m) - {w - *Rl* E (a + b)x} where *H is the reverse of w.

    You might also like