TOC |Gate-2006| Theory of Computation ( Automata)
- For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true? [GATE – 2006]
a. L is recursively enumerable, but not recursive
b. L is recursive, but not context-free
c. L is context-free, but not regular
d. L is regular
Answer : d)
- If s is a string over (0 + 1)* then let n0(s) denote the number of 0’s in s and n1(s) the number of 1’s in s. Which one of the following languages is not regular? [GATE – 2006]
a. L = {s ∈ (0+1)* | n0(s) is a 3-digit prime}
b. L = {s ∈ (0+1)* | for every prefix s’ of s,|n0(s’) – n1(s’)| ≤ 2}
c. L = {s ∈ (0+1)* |n0(s) – n1(s)| ≤ 4}
d. L = {s ∈ (0+1)* | n0(s) mod 7 = n1(s) mod 5 = 0}
Answer : c)
- In the correct grammar of above question, what is the length of the derivation (number of steps starting from S) to generate the string albm with l≠m? [GATE – 2006]
a. max(l,m)+2
b. l+m+2
c. l+m+3
d. max(l, m)+3
Answer : a)
- Which one of the following grammars generates the language L = {aibj | i≠j}? [GATE – 2006]
a. S→AC|CB
C→aCb|a|b
A→aA|ϵ
B→Bb|ϵ
b. S→aS|Sb|a|b
c. S→AC|CB
C→aCb|ϵ
A→aA|ϵ
B→Bb|ϵ
d. S→AC|CB
C→aCb|ϵ
A→aA|a
B→Bb|b
Answer : d)
- Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this language is: [GATE – 2006]
a. 3
b. 5
c. 8
d. 9
Answer : d)
- Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false? [GATE – 2006]
a. L1 ∩ L2 is a deterministic CFL
b. L3 ∩ L1 is recursive
c. L1 ∪ L2 is context free
d. L1 ∩ L2 ∩ L3 is recursively enumerable
Answer : b)
7. Consider the following statements about the context free grammar
G = {S → SS, S → ab, S → ba, S → Ε}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G? [GATE – 2006]
a. I only
b. I and III only
c. II and III only
d. I, II and III
Answer : b)
8. In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string S → aSa | bSb | a | b | ϵ Which of the following strings is NOT generated by the grammar? [GATE – 2006]
a. aaaa
b. baba
c. abba
d. babaaabab
Answer : b)
9. Which regular expression best describes the language accepted by the non-deterministic automaton below? [GATE – 2006]
a. (a + b)* a(a + b)b
b. (abb)*
c. (a + b)* a(a + b)* b(a + b)*
d. (a + b)*
Answer : a)
10. Consider the regular grammar below S → bS | aA | ϵ A → aS | bA The Myhill-Nerode equivalence classes for the language generated by the grammar are : [GATE – 2006]
a. {w ∈ (a + b)* | #a(w) is even) and {w ∈ (a + b)* | #a(w) is odd}
b. {w ∈ (a + b)* | #a(w) is even) and {w ∈ (a + b)* | #b(w) is odd}
c. {w ∈ (a + b)* | #a(w) = #b(w) and {w ∈ (a + b)* | #a(w) ≠ #b(w)}
d. {ϵ}, {wa | w ∈ (a + b)* and {wb | w ∈ (a + b)*}
Answer : a)
11. Which of the following statements about regular languages is NOT true? [GATE – 2006]
a. Every language has a regular superset
b. Every language has a regular subset
c. Every subset of a regular language is regular
d. Every subset of a finite language is regular
Answer : c)
12. Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA? [GATE – 2006]
a. {anbncn ∣ n≥0}
b. {albmcn ∣ l≠m or m≠n}
c. {anbn ∣ n≥0}
d. {ambn∣ m,n≥0}
Answer : b)
13. Let L be a context-free language and M a regular language. Then the language L ∩ M is : [GATE – 2006]
a. always regular
b. never regular
c. always a deterministic context-free language
d. always a context-free language
Answer : d)
14. Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z0, X} where Z0 is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner.
For example, the transition (s, b, X) → (t, XZ0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z0 and X (in that order) on the stack. (s, a, Z0) → (s, XXZ0) (s, ϵ, Z0) → (f, ϵ) (s, a, X) → (s, XXX) (s, b, X) → (t, ϵ) (t, b, X) → (t,.ϵ) (t, c, X) → (u, ϵ) (u, c, X) → (u, ϵ) (u, ϵ, Z0) → (f, ϵ) The language accepted by the PDA is : [GATE – 2006]
a. {albmcn | l = m = n}
b. {albmcn | l = m}
c. {albmcn | 2l = m+n}
d. {albmcn | m=n}
Answer : c)
TOC |Gate-2006|
15. In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string. S → aSAb | ϵ A → bA | ϵ The grammar generates the language : [GATE – 2006]
a. ((a + b)* b)*
b. {ambn | m ≤ n}
c. {ambn | m = n}
d. a* b*
Answer : b)
TOC |Gate-2006|
16. Let L be a regular language. Consider the constructions on L below: I. repeat (L) = {ww | w ∊ L} II. prefix (L) = {u | ∃v : uv ∊ L} III. suffix (L) = {v | ∃u : uv ∊ L} IV. half (L) = {u | ∃v : | v | = | u | and uv ∊ L} Which of the constructions could lead to a non-regular language? [GATE – 2006]
a. Only I
b. Only IV
c. Both I and IV
d. Both II and III
Answer : a)
TOC |Gate-2006|
17. Let L be a regular language. Consider the constructions on L below: repeat (L) = {ww | w ∊ L} prefix (L) = {u | ∃v : uv ∊ L} suffix (L) = {v | ∃u uv ∊ L} half (L) = {u | ∃v : | v | = | u | and uv ∊ L} Which of the constructions could lead to a non-regular language? [GATE – 2006]
a. (a + b)*
b. {ϵ, a, ab, bab}
c. (ab)*
d. {anbn | n ≥ 0}
Answer : a)
TOC |Gate-2006|