# TOC |Gate-2008| Previous Year Questions| Set-13 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

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

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

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

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

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

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

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*

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

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

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

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

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

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