TOC |Gate-2008| Previous Year Questions| Set-13

Set-15 TOC GATE 2006

TOC |Gate-2008| Theory of Computation ( Automata)

  1. Which of the following is true for the language {ap|p is a prime} ?  [GATE – 2008]

a. It is not accepted by a Turing Machine
b. It is regular but not context-free
c. It is context-free but not regular
d. It is neither regular nor context-free, but accepted by a Turing machine

Answer : d)


  1. Which of the following are decidable? I.Whether the intersection of two regular languages is infinite II.Whether a given context-free language is regular III.Whether two push-down automata accept the same language IV.Whether a given grammar is context-free  : [GATE – 2008]    

a. I and II
b. I and IV
c. II and III
d. II and IV

Answer : b)


  1. If L and L’ are recursively enumerable, then L is: [GATE – 2008]

a. Recursive
b. Regular
c. Context-free
d. Context-sensitive

Answer : a)


  1. Which of the following statements is false? [GATE – 2008]

a. Every NFA can be converted to an equivalent DFA
b. Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
c. Every subset of a recursively enumerable set is recursive
d. Every regular language is also a context-free language

Answer : c)


  1. Which of the following statements are true? I.Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa II.All e-productions can be removed from any context-free grammar by suitable transformations III.The language generated by a context-free grammar all of whose productions are of the form X ® w or X ® wY a non-terminal), is always regular (where, w is a string of  erminals and Y is IV.The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees : [GATE – 2008] 

a. I, III and IV only
b. II, III and IV only
c. I, II, III and IV
d. I, II and IV only

Answer : a)


  1. Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true? [GATE – 2008]

a. n ≤ m
b. m ≤ 2n
c. M has one accept state
d. m = 2n

Answer : b)


  1. If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA? [GATE – 2008]

a. Set of all strings that do not end with ab
b. Set of all strings that begin with either an a or a b
c. Set of all strings that do not contain the substring ab
d. The set described by the regular expression b*aa*(ba)*b*

Answer : a)


  1. Consider the following languages. L1 = {ai bj ck | i = j, k ≥ 1} L1 = {ai bj | j = 2i, i ≥ 0} Which of the following is true? [GATE – 2008]

a. L1 is not a CFL but L2 is
b. L1 ∪ L2 is not a CFL but L2 is
c. L1 ∩ L2 = ∅ and L1 is non-regular
d. There is a 4-state PDA that accepts L1, but there is no DPDA that accepts L2

Answer : c)


  1. Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B → 0B00 | 1 S is the start symbol, A and B are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is : [GATE – 2008]

a. {0n 102n | n ≥ 1}
b. {0i 10j 10k | i, j, k ≥ 0} ∪ {0n 102n | n ≥ l}
c. {0i 10j | i, j ≥ 0} ∪ {0n 102n | n ≥ l}
d. The set of all strings over {0, 1} containing at least two 0’s
e. None of the above

Answer : e)


  1. Which of the following languages is (are) non-regular? L1 = {0m1n | 0 ≤ m ≤ n ≤ 10000} L2 = {w | w reads the same forward and backward} L3 = {w ∊ {0, 1} * | w contains an even number of 0’s and an even number of 1’s}  [GATE – 2008]

a. L2 and L3 only
b. L1 and L2 only
c. L3 only
d. L2 only

Answer : d)


  1. Consider the following two finite automata. M1 accepts L1 and M2 accepts L2.

Which one of the following is TRUE? [GATE – 2008]

a. L1 = L2
b. L1 ⊂ L2
c. L1 ∩ L2‘ = ∅
d. L1 ∪ L2 ≠ L1
e. A and C

Answer : e)
TOC |Gate-2008|


  1. A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. S→aS∣A A→aAb∣bAa∣ϵ Which of the following strings is generated by the grammar above? [GATE – 2008]   

a. aabbaba
b. aabaaba
c. abababb
d. aabbaab

Answer : d)
TOC |Gate-2008|


  1. A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. S→aS∣A A→aAb∣bAa∣ϵ For the correct answer in Q75, how many steps are required to derive the string and how many parse trees are there?  [GATE – 2008]

a. 6 and 1
b. 6 and 2
c. 7 and 2
d. 4 and 2

Answer : a)
TOC |Gate-2008|


Back to GATE-HOME


Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *