# Practice Test: Question Set - 09

**1. A grammar to generate**

{ (ab)n I n ≥ 1 } ∪ { (ba)n I n ≥ 1 }**
is constructed as**

- (A) S
---> S

_{1}, S

_{1}---> abS

_{1}, S

_{1}---> ab, S ---> S

_{2}, S

_{2}—> baS

_{2}, S

_{2}—> ba

- (B) S ---> S

_{1 }, S

_{l}---> aS

_{1}, S

_{1}---> ab, S ---> S

_{2}, S

_{2}---> bS

_{2}, S

_{2}—> bc

- (C) S —> S

_{1}, S

_{1}—>S

_{2}, S

_{2}—> S

_{1}a, S

_{1}—> ab, S

_{2}—> ba

- (D) None of
these

**2. Palindromes can’t be recognized by any FSA because**

- (A) FSA cannot
remember arbitrarily large amount of information

- (B) FSA cannot
deterministically fix the midpoint

- (C) Even if the
midpoint is known an FSA cannot find whether the second half of the string
matches the first half

- (D) All of the
above

**3. Which of the following statements is correct?**

- (A) A = { If a

^{n}b

^{n}| n = 0,1, 2, 3 ..} is regular language

- (B) Set B of all
strings of equal number of a's and b's deines a regular language

- (C) L (A* B*)∩ B
gives the set A

- (D) None of
these

**4. Which of the following statement is correct?**

- (A) All
languages cannot be generated by CFG

- (B) Any regular
language has an equivalent CFG

- (C) Some non
regular languages can't be generated by CFG

- (D) Both (b) and
(c)

**5. Consider the following statements**

I. Recursive languages are closed under complementation

II. Recursively enumerable languages are closed under union III. Recursively enumerable languages are closed under complementation

Show and hide multiple DIV using JavaScript

**Which of the
above statement are TRUE?**

- (A) I only

- (B) I and II

- (C) I and III

- (D) II and III

**6. Let L be a language recognizable by a finite automaton.****The language,**

**REVERSE (L) = {w such that w is the reverse
of v where v ∈ L} is a**

- (A) Regular
language

- (B) Context-free
language

- (C) Context-sensitive
language

- (D) Recursively
enumerable language

**7. If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called**- (A) Decidable

- (B) Un-decidable

- (C) Interpretive

- (D) Non-deterministic

**8. A class of language that is closed under**- (A) Union and
complementation has to be closed under intersection

- (B) Intersection
and complement has to be closed under union

- (C) Union and
intersection has to be closed under complementation

- (D) Both (A) and
(B)

**9. CFG can be recognized by a**- (A) push-down
automata

- (B) 2-way linear
bounded automata

- (C) Both (a) and
(b)

- (D) None of
these

**10. Given a grammar G a production of G with a dot at some position of the right side is called**- (A) LR (0) item
of G

- (B) LR (1) item
of G

- (C) Both (a) and
(b)

- (D) None of these

**View All Answers****Next Tests:**