Computer Science Theory of Computation Exam Questions - Set 09 - ObjectiveBooks
Computer Science Theory of Computation Exam Questions - Set 09

Computer Science Theory of Computation Exam Questions - Set 09

Edit

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 ---> S1, S1 ---> abS1,  S1 ---> ab,  S ---> S2, S2 —> baS2, S2 —> ba
    (B) S ---> S1 , Sl ---> aS1, S1 ---> ab, S ---> S2, S2 ---> bS2, S2 —> bc
    (C) S —> S1,  S1—>S2, S2 —> S1a, S1 —> ab, S2 —> 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 an bn  | 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

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
Show and hide multiple DIV using JavaScript View All Answers
 Next Tests:

    Blogger Comment
    Facebook Comment