Automata GATE CS and IT previous year questions with answer

Ques 41 Gate 2016 Set-2

---

Language L1 is defined by the grammar:
S1 -> aS1b | ε
Language L2 is defined by the grammar:
S2 -> abS2 | ε
Consider the following statements:

P: L1 is regular
Q: L2 is regular

Which one of the following is TRUE?

A

Both P and Q are true

B

P is true and Q is false

C

P is false and Q is true

D

Both P and Q are false

See Answer Video Solution

Ques 42 Gate 2016 Set-1

---

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y reduces to W, and Z reduces to X (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

A

W can be recursively enumerable and Z is recursive.

B

W an be recursive and Z is recursively enumerable.

C

W is not recursively enumerable and Z is recursive.

D

W is not recursively enumerable and Z is not recursive

See Answer Video Solution

Ques 43 Gate 2016 Set-1

---

Consider the following context-free grammars:

Which one of the following pairs of languages is generated by G1 and G2, respectively?

A

{a^mbⁿ |m > 0 or n > 0} and {a^mbⁿ |m > 0 and n > 0}

B

{a^mbⁿ |m > 0 and n > 0} and {a^mbⁿ |m > 0 or n ≥ 0}

C

{a^mbⁿ |m ≥ 0 or n > 0} and {a^mbⁿ |m > 0 and n > 0}

D

{a^mbⁿ |m ≥ 0 and n > 0} and {a ^mbⁿ |m > 0 or n > 0}

See Answer Video Solution

Ques 44 Gate 2016 Set-1

---

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

A

(0+1)*0011(0+1)* + (0+1)*1100(0+1)*

B

(0+1)* (00(0+1) *11+11(0+1)*00)(0+1)*

C

(0+1)*00(0+1) *+ (0+1) *11(0+1) *

D

00(0+1) *11+11(0+1)*00

See Answer Video Solution

Ques 45 Gate 2016 Set-1

---

Which of the following decision problems are undecidable?

I. Given NFAs N₁ and N₂, is L(N₁)∩L(N₂) = Φ?
II. Given a CFG G = (N,Σ,P,S) and a string x ∈ Σ*, does x ∈ L(G)?
III. Given CFGs G₁ and G₂, is L(G₁) = L(G₂)?
IV. Given a TM M, is L(M) = Φ?

A

I and IV only

B

II and III only

C

III and IV only

D

II and IV only

See Answer Video Solution

Ques 46 Gate 2016 Set-1

---

Which of the following languages is generated by the given grammar?

S → aS|bS| ε

A

{aⁿb^m | m,n >= 0}

B

{w∈{a,b}* | w has equal number of a's and b's}

C

{aⁿ | n>=0} U {aⁿbⁿ | n>=0}

D

{a,b}*

See Answer Video Solution

Ques 47 Gate 2015 Set-1

---

For any two languages L₁ and L₂ such that L₁ is context free and L₂ is recursively enumerable but not recursive, which of the following is/are necessarily true?

A

I only

B

III only

C

III and IV only

D

I and IV only

See Answer Video Solution

Ques 48 Gate 2014 Set-1

---

Which one of the following is TRUE?

A

The Language L={ aⁿ bⁿ | n≥ is regular }

B

The Language L={ aⁿ | n is prime }

C

The Language L={ w | w has 3k+1 b's for some k ∈ N with Σ ={a,b}} is regular

D

The Language L={ww | w ∈ Σ with Σ ={0,1}} is regular

See Answer Video Solution