Theory of Computation MCQ pdf Download - Set 03 - ObjectiveBooks
Theory of Computation MCQ pdf Download - Set 03

Theory of Computation MCQ pdf Download - Set 03

Practice Test: Question Set - 03

1. FSM can recognize
    (A) Any grammar
    (B) Only CG
    (C) Both (a) and (b)
    (D) Only regular grammar
2. Consider a grammar with the following productions

    S-->   aab | bac | aB
    S -->  α S |
    S -->  α b b | ab
    Sα --> bdb | b
The above grammar is

    (A) Context free
    (B) Regular
    (C) Context sensitive
    (D) LR (k)
3. Which of the following statement is wrong?
    (A) Any regular language can be generated by a context-free grammar
    (B) Some non-regular languages cannot be generated by any CFG
    (C) The intersection of a CFL and regular set is a CFL
    (D) All non-regular languages can be generated by CFGs
4. Which of the following conversion is not possible (algorithmically)?
    (A) Regular grammar to context-free grammar
    (B) Nondeterministic FSA to deterministic FSA
    (C) Nondeterministic PDA to deterministic PDA
    (D) Nondeterministic TM to deterministic TM
5. The grammars G = ( { s }, { 0, 1 }, p , s)

     where, p = (s —> 0S1, S —> OS, S —> S1, S —>0} is a

    (A) Recursively enumerable language
    (B) Regular language
    (C) Context-sensitive language
    (D) Context-free language
6. The following grammar

    G = (N, T, P, S)

    N = {S, A, B, C, D, E}
     T = {a, b, c}
     P : S ? aAB
     AB ? CD
     CD ? CE
     C ? aC
     C ? b
     bE ? bc 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
7. (a + b)(cd)*(a + b) denotes the following set
    (A) {a(cd)nb|n = 1}
    (B) {a(cd)na|n = 1} ? {b(cd)nb/n = 1}
    (C) {a(cd)na|n = 0} ? {a(cd)nb/n = 0} ? {b(cd)na/n = 0} ? {b(cd)nb/n = 0}
    (D) {acndnb|n = 1}
8. If L be a language recognizable by a finite automaton, then language front 

{L} = { w such that w is prefix of v where v ∈ L },  is a

    (A) Regular language
    (B) Context-free language
    (C) Context-sensitive language
    (D) Recursive enumeration language
9. The following grammar

    G = (N, T, P, S)

    N = {S, A, B, C}
     T = {a, b, c}
     P : S ? aS
     A ? bB
     B ? cC
     C ? a 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
10. If a language is denoted by a regular expression

L = ( x )* (x | y x ) ,
then which of the following is not a legal string within L ?

    (A) yx
    (B) xyx
    (C) x
    (D) x y x y x
Show and hide multiple DIV using JavaScript View All Answers
 Next Tests: