Theory of Computation MCQs with Answers - Set 04 - ObjectiveBooks
Theory of Computation MCQs with Answers - Set 04

Theory of Computation MCQs with Answers - Set 04

Edit

Practice Test: Question Set - 04

1. The defining language for developing a formalism in which language definitions can be stated, is called
    (A) Syntactic meta language
    (B) Decidable language
    (C) Intermediate language
    (D) High level language
2. Consider the following language,

    L = {anbn|n = 1}

L is?

    (A) CFL but not regular
    (B) CSL but not CFL
    (C) Regular
    (D) Type 0 language but not type 1
3. Can a DFSA simulate a NFSA
    (A) No
    (B) Yes
    (C) Sometimes
    (D) Depends on NFA
4. A language L is accepted by a FSA if it is
    (A) CFL
    (B) CSL
    (C) Recursive
    (D) Regular
5. Recursively enumerable languages are not closed under
    (A) Union
    (B) Homomorphism
    (C) Complementation
    (D) Concatenation
6. Grammar

    S —> a,
    S —> A3A4 ,
    A3 —> A1, A3, A2 ,
    A3 —> A1 A2, A1
    A2—> aA2A1 ,
    A1a —> a A1, 
    A2a —> aA2, 
    A1A4 —> A4a,
    A2A4 —> A5a, 
    A2A5 —> A5a,
    A5 —> a
generates

    (A) an^2
    (B) n2a
    (C) 2an
    (D) None of these
7. Which one of the following statement is FALSE?
    (A) Context-free languages are closed under union
    (B) Context-free languages are closed under concatenation
    (C) Context-free languages are closed under intersection
    (D) Context-free languages are closed under Keene closure
8. Correct hierarchical relationship among context- free, right-linear, and context-sensitive language is
    (A) Context-free ⊂ right-linear ⊂ context-sensitive
    (B) Context-free ⊂ context-sensitive ⊂ right-linear
    (C) Context-sensitive ⊂ right-linear ⊂context-free
    (D) Right-linear ⊂context-free ⊂context-sensitive
9. The CFG 

    s---> as | bs |  a |  b

Is equivalent to regular expression?

    (A) (a + b)
    (B) (a + b) (a + b)*
    (C) (a + b) (a + b)
    (D) None of these
10. Consider the following language,

    L = {anbncndn|n = 1}

L is?

    (A) CFL but not regular
    (B) CSL but not CFL
    (C) Regular
    (D) Type 0 language but not type 1
Show and hide multiple DIV using JavaScript View All Answers
 Next Tests:

    Blogger Comment
    Facebook Comment