Scribd Logo
Upload

Welcome to Scribd!

  • 45 views

    T F, CS-5800 Sample Exam 1

    Uploaded by

    deewanagan
    This document contains a sample exam for a theory of computation course. It includes 9 questions covering topics like: - Proving properties of strings and languages using induction - Defining common formal language concepts like equivalence relations, bijections, countable/uncountable sets, regular expressions, DFAs, regular grammars - Proving properties of sets like countability and closure under operations - Describing the Chomsky hierarchy and characteristic grammar rules for each language type - Simulating a DFA on an input string and analyzing the time complexity

    Copyright:

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

    T F, CS-5800 Sample Exam 1

    Uploaded by

    deewanagan
    45 views2 pages
    This document contains a sample exam for a theory of computation course. It includes 9 questions covering topics like: - Proving properties of strings and languages using induction - Defining common formal language concepts like equivalence relations, bijections, countable/uncountable sets, regular expressions, DFAs, regular grammars - Proving properties of sets like countability and closure under operations - Describing the Chomsky hierarchy and characteristic grammar rules for each language type - Simulating a DFA on an input string and analyzing the time complexity

    Original Description:

    Sample exam

    Original Title

    t1f14-5800sample

    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 a sample exam for a theory of computation course. It includes 9 questions covering topics like: - Proving properties of strings and languages using induction - Defining common formal language concepts like equivalence relations, bijections, countable/uncountable sets, regular expressions, DFAs, regular grammars - Proving properties of sets like countability and closure under operations - Describing the Chomsky hierarchy and characteristic grammar rules for each language type - Simulating a DFA on an input string and analyzing the time complexity

    Copyright:

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

    T F, CS-5800 Sample Exam 1

    Uploaded by

    deewanagan
    This document contains a sample exam for a theory of computation course. It includes 9 questions covering topics like: - Proving properties of strings and languages using induction - Defining common formal language concepts like equivalence relations, bijections, countable/uncountable sets, regular expressions, DFAs, regular grammars - Proving properties of sets like countability and closure under operations - Describing the Chomsky hierarchy and characteristic grammar rules for each language type - Simulating a DFA on an input string and analyzing the time complexity

    Copyright:

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

    THEORY FOUNDATIONS, CS-5800

    Sample Exam 1
    CLOSED BOOK, CLOSED NOTES
    Your name:
    1. Prove by induction:
    2 + 5 + 8 + + (3n 1) =
    n(3n + 1)
    2
    , for n > 0.
    2. If u and v are strings, u, v

    , prove that (uv)


    R
    = v
    R
    u
    R
    , by induction on the length of v.
    3. Dene:
    (i) an equivalence relation;
    (ii) a bijection;
    (iii) a countable set;
    (iv) a language over an alphabet ;
    (v) (give a recursive denition of:) the length of a string;
    (vi) (give a recursive denition of:) a regular set, and of a regular expression (Basis: What are the primitive
    regular expressions? Recursive step? Closure: Explain.
    (vii) a DFA (give formal denition: as a 5-tuple; explain all elements of the 5-tuple, including the mapping
    of the transition function );
    (viii) a regular grammar, a CFL.
    4. Consider the set A of all total functions which map from the set N of the natural numbers to the set {0, 1}
    of the two elements 0 and 1:
    A = { f total function | f : N {0, 1} }.
    Prove by (Cantor) diagonalization that the set A is uncountable.
    5. Prove that the set Z of all integers,
    Z = { , 3, 2, 1, 0, 1, 2, 3, }
    is countably innite.
    1
    6. (i) Let X be a set. Dene:
    a) X

    b) X
    +
    (ii) Let X = { a, b, c }; Y = { ccb, d }.
    Express:
    a) XY
    b) X
    0
    c) XX = X
    2
    7. Exercise: Show that the set of the regular languages is closed under union, concatenation and Kleene closure.
    8. For a given DFA and a particular string, give a computation on the string. Is the string accepted or rejected?
    Give an algorithm to simulate a DFA. Work through it for an example DFA and string. What is the time
    complexity of the algorithm as a function of the length of the string?
    9. Give an overview of the Chomsky hierarchy of languages and their grammars, with the characteristic form
    of the grammar rules for each type.
    2

    You might also like