Theory of Computation MCQ Questions - Set 01 - ObjectiveBooks
Theory of Computation MCQ Questions - Set 01

Theory of Computation MCQ Questions - Set 01

Practice Test: Question Set - 01

1. Basic limitation of FSM is that it
    (A) Cannot remember arbitrary large amount of information
    (B) Sometimes fails to recognize grammars that are regular
    (C) Sometimes recognizes grammars are not regular
    (D) None of these
2. The language of all words with at least 2 a's can be described by the regular expression
    (A) (ab)*a and a (ba)*
    (B) (a + b)* ab* a (a + b)*
    (C) b* ab* a (a + b)*
    (D) All of these
3. Given A = (0,1) and L = A*. If R = (0n 1n, n > 0) , then language L ∪ R and R are respectively
    (A) Regular, regular
    (B) Not regular, regular
    (C) Regular, not regular
    (D) Context free, not regular
4. The following grammar
     G = (N, T, P, S)
     N = {S, A, B, C, D, E}
     T = (a, b, c}
     P : S ? ABCD
     BCD ? DE
     D ? aD
     D ? a
     E ? bE
     E ? c is
    (A) Is type 3
    (B) Is type 2 but not type 3
    (C) Is type 1 but not type 2
    (D) Is type 0 but not type 1
5. The following CFG is in
    S ? aBB
     B ? bAA
     A ? a
     B ? b
    (A) Chomsky normal form but not strong Chomsky normal form
    (B) Weak Chomsky normal form but not Chomsky normal form
    (C) Strong Chomsky normal form
    (D) Greibach normal form
6. In a context-sensitive grammar, number of grammar symbols on the left hand side of a production can't be greater than the number of
    (A) Grammar symbols on the right hand side
    (B) Terminals on the right hand side
    (C) Non-terminals on the right hand side
    (D) All of these
7. Which of the following denotes Chomskian hiearchy?
    (A) REG ? CFL ? CSL ? type0
    (B) CFL ? REG ? type0 ? CSL
    (C) CSL ? type0 ? REG ? CFL
    (D) CSL ? CFL ? REG ? type0
8. The intersection of CFL and regular language
    (A) Is always regular
    (B) Is always context free
    (C) Both (a) and (b)
    (D) Need not be regular
9. Consider a language L for which there exists a Turing machine TM, T, that accepts every word in L and either rejects or loops for every word not in L. The language L is
    (A) NP hard
    (B) NP complete
    (C) Recursive
    (D) Recursively enumerable
10. Which of the following statements is (are) correct?
    (A) Recursive languages are closed under complementation
    (B) If a language and its complement are both regular, the language is recursive
    (C) Set of recursively enumerable language is closed under union
    (D) All of these
Show and hide multiple DIV using JavaScript View All Answers
 Next Tests: