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

- Which of the following is true for the language {a
^{p}|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)*

- 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)*

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

a. Recursive

b. Regular

c. Context-free

d. Context-sensitive

*Answer : a)*

- 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)*

- 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)*

- 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 ≤ 2^{n}

c. M has one accept state

d. m = 2^{n}

*Answer : b)*

- 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)*

- Consider the following languages. L
_{1}= {a^{i}b^{j}c^{k}| i = j, k ≥ 1} L_{1}= {a^{i}b^{j}| j = 2i, i ≥ 0} Which of the following is true?**[GATE – 2008]**

a. L_{1} is not a CFL but L_{2} is

b. L_{1} ∪ L_{2} is not a CFL but L_{2} is

c. L_{1} ∩ L_{2} = ∅ and L_{1} is non-regular

d. There is a 4-state PDA that accepts L_{1}, but there is no DPDA that accepts L_{2}

*Answer : c)*

- 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. {0^{n} 10^{2n} | n ≥ 1}

b. {0^{i} 10^{j} 10^{k} | i, j, k ≥ 0} ∪ {0^{n} 10^{2n} | n ≥ l}

c. {0^{i} 10^{j} | i, j ≥ 0} ∪ {0^{n} 10^{2n} | n ≥ l}

d. The set of all strings over {0, 1} containing at least two 0’s

e. None of the above

*Answer : e)*

- Which of the following languages is (are) non-regular? L
_{1}= {0^{m}1^{n}| 0 ≤ m ≤ n ≤ 10000} L_{2}= {w | w reads the same forward and backward} L_{3}= {w ∊ {0, 1} * | w contains an even number of 0’s and an even number of 1’s}**[GATE – 2008]**

a. L_{2} and L_{3} only

b. L_{1} and L_{2} only

c. L_{3} only

d. L_{2} only

*Answer : d)*

- Consider the following two finite automata. M
_{1}accepts L_{1}and M_{2}accepts L_{2}.

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

a. L_{1} = L_{2}

b. L_{1} ⊂ L_{2}

c. L_{1} ∩ L_{2}‘ = ∅

d. L_{1} ∪ L_{2} ≠ L_{1}

e. A and C

*Answer : e)*

TOC |Gate-2008|

- 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|

- 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|