Scribd Logo
Upload

Welcome to Scribd!

  • 41 views

    Bachelor in Computer Applications Term-End Examination June, 2012 Cs-73: Theory of Computer Science

    Uploaded by

    Ranbir Singh
    This document contains a 3 page exam for a Theory of Computer Science course. It includes 7 questions testing knowledge of Chomsky hierarchy, Turing machines, recursive languages, finite automata, regular expressions, undecidability, pushdown automata, context free languages, complexity analysis, and applications of automata. Students are asked to define concepts, prove properties of languages, convert between models of computation, analyze algorithms, and describe applications.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Bachelor in Computer Applications Term-End Examination June, 2012 Cs-73: Theory of Computer Science

    Uploaded by

    Ranbir Singh
    41 views3 pages
    This document contains a 3 page exam for a Theory of Computer Science course. It includes 7 questions testing knowledge of Chomsky hierarchy, Turing machines, recursive languages, finite automata, regular expressions, undecidability, pushdown automata, context free languages, complexity analysis, and applications of automata. Students are asked to define concepts, prove properties of languages, convert between models of computation, analyze algorithms, and describe applications.

    Original Description:

    question paper

    Original Title

    CS-73

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains a 3 page exam for a Theory of Computer Science course. It includes 7 questions testing knowledge of Chomsky hierarchy, Turing machines, recursive languages, finite automata, regular expressions, undecidability, pushdown automata, context free languages, complexity analysis, and applications of automata. Students are asked to define concepts, prove properties of languages, convert between models of computation, analyze algorithms, and describe applications.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    41 views3 pages

    Bachelor in Computer Applications Term-End Examination June, 2012 Cs-73: Theory of Computer Science

    Uploaded by

    Ranbir Singh
    This document contains a 3 page exam for a Theory of Computer Science course. It includes 7 questions testing knowledge of Chomsky hierarchy, Turing machines, recursive languages, finite automata, regular expressions, undecidability, pushdown automata, context free languages, complexity analysis, and applications of automata. Students are asked to define concepts, prove properties of languages, convert between models of computation, analyze algorithms, and describe applications.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    No.

    of Printed Pages : 3 BACHELOR IN COMPUTER APPLICATIONS Term-End Examination

    CS-73

    oo O

    June, 2012 CS-73 : THEORY OF COMPUTER SCIENCE Time : 3 hours Maximum Marks : 75

    Note : Question no. 1 is compulsory. Attempt any three questions from the rest.

    1.

    (a) (b) (c)

    Tabulate chomsky hierarchy of grammar with examples. Briefly describe Universal Turing Machine. If L is recursive, show that E is also recursive. Using parse tree show that the grammar : S -* S +S S*S a is ambigous Use a + a*a as the string List three applications of finite Automata. Convert the following Regular expression into FA : (a + b) * (aa + bb) (a +b)* When can a problem be termed as undecidable ? Explain with example. 1

    5 5 4 4

    (d)

    (e) (f)

    3 5

    (g)

    CS-73

    P.T.O.

    2.

    (a) Derive FA from the following NFA :


    b

    (b)

    Convert the following Regular expression into a FA : a*(ba) * b * Give Regular Expression for all strings that do not end in a double letter.

    (c)

    3.

    (a) Show that the language : L = lanbn : n 01 is not regular. (b) (c) Design a TM that accepts all strings over alphabet = {a, b} whose second letter is b.

    6 5

    Explain with example Non Deterministic 4 Turing Machine (NDTM).

    4.

    (a) Build a PDA for language described as : L= {ambm J m31} (b) (c) Show that the language : L = {anbno : 0} is not context free. Show that the function is primitive recursive f (n, n) = {m 0 n if m nj else

    5 5

    CS-73

    5.

    (a) If f (x)=2x3 + 3x2 + 1 then show that


    f (x)= 0 (x)

    and also f (x)= 0 (x2). (b) (c) What is meant by time complexity and space complexity of a problem ? 3

    Explain how a finite Automata can be used 6 to search information on world wide web ?

    CS-73

    You might also like