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
Next Tests: