TOC |Gate-2008| Theory of Computation ( Automata)
- 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)
- 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 ≤ 2n
c. M has one accept state
d. m = 2n
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. 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)
- 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)
- 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)
- 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|
- 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|