# Practice Test: Question Set - 10

**1. Which of the following definitions below generates the same language as L, where**

L = {xn yn such that n > = 1} ?

I. E —> xEy | xy- (A) I only

- (B) I and II

- (C) II and III

- (D) II only

**2. Following context free grammar**

S —> aB | bA

A —>b | aS | bAA

B —> b | bS | aBB **
generates strings of terminals that have**

- (A) Equal number
of a's and b's

- (B) Odd number
of a's and odd number b's

- (C) Even number
of a's and even number of b's

- (D) Odd number
of a's and even number of a's

**3. Set of regular languages over a given alphabet set is closed under**

- (A) Union

- (B) Complementation

- (C) Intersection

- (D) All of these

**4. Consider the grammar:**

S —> ABCc | Abc

BA —> AB

Bb —> bb

Ab —> ab

Aa —> aa

**Which of the following sentences can be
derived by this grammar?**

- (A) abc

- (B) aab

- (C) abcc

- (D) abbb

**5. Define for a context free language**

L ≤ {0 ; 1} init (L) = {u/uv Îµ L for some v in {0,1}}

(in other words, init (L) is the set of prefixes of L)

Let L {w/w is noempty and has an equal number of 0’s and 1’s)**
Then init (L) is**

- (A) Set of all
binary strings with unequal number of 0’s and 1’s

- (B) Set of all
binary strings including the null string

- (C) Set of all
binary strings with exactly one more 0’s than the number of 1’s or 1 more
than the number of 0’s

- (D) None of
these

**6. Which of the following conversion is not possible (algorithmically)?**

- (A) Regular
grammar to context-free grammar

- (B) Nondeterministic
FSA to deterministic FSA

- (C) Nondeterministic
PDA to deterministic PDA

- (D) Nondeterministic
TM to deterministic TM

**7. For two regular languages**

L_{1} = (a + b)* a and L_{2} =
b (a + b) ***
The intersection of L _{1} and L_{2} is given by **

- (A) (a + b ) *
ab

- (B) ab (a + b )
*

- (C) a ( a + b )
* b

- (D) b (a + b ) *
a

**8. For which of the following application, regular expressions cannot be used?**

- (A) Designing
computers

- (B) Designing
compilers

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

- (D) Developing
computers

**9. If G = ({S}, {a}, {S -> SS), S),**

**
then language generated by G is**

- (A) L (G) = Ï†

- (B) L(G) = a

^{n}

- (C) L (G) = a*

- (D) L (G) = a

^{n}ba

^{n}

**10. Recursively enumerable languages are not closed under**

- (A) Union

- (B) Homomorphism

- (C) Complementation

- (D) Concatenation

Show and hide multiple DIV using JavaScript
View All Answers

**Next Tests:**

Blogger Comment

Facebook Comment