Theory of Computation Multiple Choice Questions - Set 08 - ObjectiveBooks

# 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: