Theory of Computation Objective Questions & Answers - ObjectiveBooks
Theory of Computation Objective Questions & Answers

Theory of Computation Objective Questions & Answers

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: