# 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) n

^{2}

- (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 {a

^{n}| n is odd}

- (B) L must be {a

^{n}| n is even}

- (C) L must be {a

^{n}| > 0}

- (D) Either L
must be {a

^{n}| n is odd}, or L must be {a

^{n}| 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

**View All Answers**

**Next Tests:**

Blogger Comment

Facebook Comment