Theory of Computation MCQ Test - Set 07 - ObjectiveBooks
Theory of Computation MCQ Test - Set 07

Theory of Computation MCQ Test - Set 07

Edit

Practice Test: Question Set - 07

1. Which of the following problem is un-decidable?
    (A) Membership problem for CFL
    (B) Membership problem for regular sets
    (C) Membership problem for CSL
    (D) Membership problem for type 0 languages
2. Consider a grammar:

     G = { { S } , { 0 , 1 } , p , s } 
where elements of p are:
    S --> ss
    S--> 0S1
    S--> 1S0
    S--> empty
The grammar will generate

    (A) Regular language
    (B) Context-free language
    (C) Context-sensitive language
    (D) Recursive enumerable language
3. Context free language are closed under
    (A) Union, intersection
    (B) Union, Kleene closure
    (C) Intersection, complement
    (D) Complement, Kleene closure
4. Following syntax-directed translation scheme is used with a shift reduction (bottom up) parser that perform the action in braces immediately after a reduction by the corresponding production

    A  —> aB  {print “(1)” A —> c {print “1”),
    B —> Ab  {print *2”}.
When parser is aaacbbb, then string printed

    (A) 0202021
    (B) 1202020
    (C) 1020202
    (D) None of these
5. Which of the following CF language is inherently ambiguous?
    (A) {anbncmdm|n, m = 1}
    (B) {anbmcpdq|n = p or m = q, n, m, p, q = 1}
    (C) {anbmcpdq|n ? m ? p ? q}
    (D) {anbmcpdq|n ? m ? p ? q}
6. ADG is said to be in Chomsky Form (CNF), if all the productions are of the form A --> BC or A --> a. Let G be a CFG in CNF. To derive a string of terminals of length x , the number of productions to be used is
    (A) 2x - 1
    (B) 2x
    (C) 2x + I
    (D) None of these
7. Which of the following is not primitive recursive but partially recursive?
    (A) McCarthy’s function
    (B) Riemann function
    (C) Ackermann’s function
    (D) Bounded function
8. Which of the following is not possible algorithmically?
    (A) Regular grammar to context free grammar
    (B) Non-deterministic FSA to deterministic FSA
    (C) Non-deterministic PDA to deterministic PDA
    (D) None of these
9. If Î£ = (0, 1), L = Σ* and R = (0n 1nsuch that n > 0), then languages L ∪ R and R respectively are
    (A) Regular, Regular
    (B) Regular, Not regular
    (C) Not regular, Not regular
    (D) None of these
10. A given grammar is called ambiguous if
    (A) Two or more productions have the same non-terminal on the left hand side
    (B) A derivation tree has more than one associated sentence
    (C) There is a sentence with more than one derivation tree corresponding to it
    (D) Brackets are not present in the grammar
Show and hide multiple DIV using JavaScript View All Answers
 Next Tests:

    Blogger Comment
    Facebook Comment