APSET JULY 2012 QUESTION PAPER WITH ANSWER KEY COMPUTER SCIENCE

Recommend US on google

If you like the blog, Please click on recommend us on google button below

Followers

Automata Theory


31.Consider a language L for which there exists a Turing machine (TM), T, that accepts every word in Land either rejects or loops for every word that is not in L. The language L is
  1. NP hard
  2. NP complete
  3. recursive
  4. recursively enumerable
32.Consider the following statements
  1. Recursive languages are closed under complementation
  2. Recursively enumerable languages are closed under union
  3. Recursively enumerable languages are closed under complementation
Which of the above statement are TRUE?
  1. I only
  2. I and II
  3. I and III
  4. II and III
33.Which of the following statement is wrong?
  1. Any regular language can be generated by a context-free grammar
  2. Some non-regular languages cannot be generated by any CFG
  3. the intersection of a CFL and regular set is a CFL
  4. All non-regular languages can be generated by CFGs.
34.Recursively enumerable languages are not closed under
  1. union
  2. homomorphism
  3. complementation
  4. concatenation
35.Which of the following problem is undecidable?
  1. membership problem for CFL
  2. membership problem for regular sets
  3. membership problem for CSL
  4. membership problem for type 0 languages
36.Recursive languages are
  1. a proper superset of CFL
  2. always recognized by PDA
  3. are also called type 0 languages
  4. always recognized by FSA
37.R1 and R2 are regular sets. Which of the following is not true?
  1. R1 ∩ R2 neet not be regular
  2. Σ* − R1 is regular
  3. R1 ∪ R2 is regular
  4.  is regular
38.Which of the following regular expression identity is true?
  1. r(*) = r*
  2. (r*s*)* = (r + s)*
  3. (r + s)* = r* + s*
  4. r*s* = r* + s*
39.Which one of the following statement is FALSE?
  1. context-free languages are closed under union
  2. context-free languages are closed under concatenation
  3. context-free languages are closed under intersection
  4. context-free languages are closed under Kleene closure
40.Which of the following conversion is not possible (algorithmically)?
  1. regular grammar to context-free grammar
  2. nondeterministic FSA to deterministic FSA
  3. nondeterministic PDA to deterministic PDA
  4. nondeterministic TM to deterministic TM

31.d
32.b
33.d
34.c
35.d
36.a
37.a
38.b
39.c
40.c
Previous

2 comments:

Subscribe to: Posts (Atom)