Theory of Computation Multiple Choice Questions - Set 08 - ObjectiveBooks
Theory of Computation Multiple Choice Questions - Set 08

Theory of Computation Multiple Choice Questions - Set 08

Practice Test: Question Set - 08

1. Recursive languages are
    (A) A proper superset of CFL
    (B) Always recognized by PDA
    (C) Are also called type 0 languages
    (D) Always recognized by FSA
2. Consider the following grammar

    S --> Ax / By
    A --> By/Cw
    B --> x / Bw
    C--> y
Which of the regular expressions describe the same set of strings as the grammar?

    (A) xw * y + xw * yx + ywx
    (B) xwy + xw * xy + ywx
    (C) xw * y + xw x yx + ywx
    (D) xw xy + xww * y + ywx
3. The language L = (0n 1n 2n where n > 0) is a
    (A) Context free language
    (B) Context-sensitive language
    (C) Regular language
    (D) Recursive enumerable language
4. baa*c denotes the set
    (A) {bnamcp|n, m, p = 1}
    (B) {banc|n = 0}
    (C) {banc|n = 1}
    (D) {w|w is a string of a, b, c}
5. Consider the grammar

    S ---> PQ | SQ | PS
    P ---> x
    Q-->   y
To get a string of n terminals, the number of productions to be used is

    (A) n2
    (B) n + 1
    (C) 2n
    (D) 2n - 1
6. Let S = {a, b, c, d, e}. The number of strings in S* of length 4 such that no symbol is used more than once in a string
    (A) 360
    (B) 120
    (C) 35
    (D) 36
7. P, Q, R are three languages, if P and R are regular and if PQ = R, then
    (A) Q has to be regular
    (B) Q cannot be regular
    (C) Q need not be regular
    (D) Q cannot be a CFL
8. Any string of terminals that can be generated by the following CFG is

    S-> XY
    X--> aX | bX | a 
    Y-> Ya  | Yb | a

    (A) Has at least one 'b'
    (B) Should end in a 'a'
    (C) Has no consecutive a's or b's
    (D) Has at least two a's
9. What can be said about a regular language L over {a} whose minimal finite state automation has two states?
    (A) L must be {an | n is odd}
    (B) L must be {an | n is even}
    (C) L must be {an | > 0}
    (D) Either L must be {an | n is odd}, or L must be {an | n is even}
10. Which of the following statement is wrong?
    (A) Any regular language has an equivalent context-free grammar
    (B) Some non-regular languages can’t be generated by any context-free grammar
    (C) Intersection of context free language and a regular language is always context-free
    (D) All languages can be generated by context- free grammar
Show and hide multiple DIV using JavaScript View All Answers
 Next Tests: