Theory of Computation Objective Questions & Answers - ObjectiveBooks
Hello everybody! You can translate the content of this page by selecting a language in the select box.

# 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     II. xy | (x+ xyy+)     III .x+y+
(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

L1 = (a + b)* a and L2 = b (a + b) *
The intersection of L1 and L2 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) = an
(C) L (G) = a*
(D) L (G) = anban

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