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