# TOC |Gate-2017| Previous Year Questions| Set-4

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

1. Consider the following context-free grammar over the alphabet Σ = {a, b, c} with S as the start symbol: [GATE – 2017]

S → abScT | abcT
T → bT | b

Which one of the following represents the language generated by the above grammar?

a. {(ab)n (cb)n│n ≥ 1}
b. {(ab)n cb(m1 ) cb(m2 )…cb(mn )│n,m1,m2,…,mn ≥ 1}
c. {(ab)n (cbm)n│m,n ≥ 1}
d. {(ab)n (cbn)m│m,n ≥ 1}

Answer : b)

2. Consider the language L given by the regular expression (a+b)*b(a+b) over the alphabet {a,b}. The smallest number of states needed in deterministic finite-state automation (DFA) accepting L is _________.  [GATE – 2017]

a. 4
b. 5
c. 6
d. 7

Answer : a)

3. If G is a grammar with productions

S → SaS | aSb | bSa | SS | ϵ

where S is the start variable, then which one of the following strings is not generated by G? [GATE – 2017]

a. abab
b. aaab
c. abbaa
d. babba

Answer : d)

4. Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals. [GATE – 2017]

G1: S → aSb|T, T → cT|ϵ
G2: S → bSa|T, T → cT|ϵ

The language L(G1) ∩ L(G2) is

a. Finite
b. Not finite but regular
c. Context-Free but not regular
d. Recursive but not context-free

Answer : b)

5. Consider the following languages over the alphabet Σ = {a, b, c}.
Let L1 = {an bn cm│m,n ≥ 0} and L2 = {am bn cn│m,n ≥ 0}

Which of the following are context-free languages? [GATE – 2017]

I. L1 ∪ L2
II. L1 ∩ L2

a. I only
b. II only
c. I and II
d. Neither I nor II

Answer : a)

6. Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let Ldenote the language {x # f(x)│x ∈ A* }. Which of the following statements is true: [GATE – 2017]

a. f is computable if and only if Lf is recursive.
b. If f is computable then Lf is recursive, but not conversely.
c. If f is computable then Lf is recursively enumerable, but not conversely.
d. f is computable if and only if Lf is recursively enumerable.

Answer : a)

7. Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT? [GATE – 2017]

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

Answer : b)
TOC |Gate-2017|

8. Identify the language generated by the following grammar, where S is the start variable. [GATE – 2017]

S → XY
X → aX|a
Y → aYb|ϵ

a. {am bn │ m ≥ n, n > 0}
b. {am bn │ m > n, n > 0}
c. {am bn │ m > n, n ≥ 0}
d. {am bn │ m ≥ n, n ≥ 0}

Answer : c)

9. The minimum possible number of a deterministic finite automation that accepts the regular language L = {w1aw2 | w1, w2 ∈ {a,b}*, |w1| = 2,|w2| ≥ 3} is _________.  [GATE – 2017]

a. 8
b. 9
c. 10
d. 11

Answer : a)
TOC |Gate-2017|

10. Consider the following languages:

L1 = {ap│p is a prime number}
L2 = {an bm c2m | n ≥ 0, m ≥ 0
}
L3 = {an bn c2n │ n ≥ 0}
L4 = {an bn │ n ≥ 1}

Which of the following are CORRECT? [GATE – 2017]

I. L1 is context-free but not regular.
II. L2 is not context-free.
III. L3  is not context-free but recursive.
IV. L4 is deterministic context-free.

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

Answer : d)
TOC |Gate-2017|

11. Let L(R) be the language represented by regular expression R, Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. [GATE – 2017]

Which of the following decision problems are undecidable?

I. Given a regular expression R and a string w, is w ∈ L(R)?
II. Given a context-free grammar G, is L(G) = ∅?
III. Given a context-free grammar G, is L(G) = Σ* for some alphabet Σ?
IV. Given a Turing machine M and a string w, is w ∈ L(M)?

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

Answer : b)

Back to GATE-HOME

Spread the love