Time Left - 45:00 mins

# GATE CS 2021 : Theory of Computation 7 (App update required to attempt this test)

Attempt now to get your rank among 615 students!

Question 1

Consider the following context free language (CFL)

L={anbn | n>=1}{anb2n | n>=1}

A minimum number of states that are present in the state transition diagram of the above CFL

Question 2

What is the equivalent CFL for the following CFG ?

S -> 0S1 / ϵ

Question 3

Consider the following problems

A) L is a context sensitive language (CSL), complement of L is of same type.

B) Let L1 and L2 is CSL, intersection of L1 and L2 is empty or not.

C) Finiteness problem in CFGs.

D) Emptiness problem for CFGs

Number of problems that are decidable is ____.

Question 4

consider the following statements

Statement 1- If S1 and S2 are countable sets, then union of S1 and S2 is countable.

Statement 2- The cartesian product or union of finite countable sets may or may not be countable.

Statement 3- The set of all languages that are not recursively enumerable is uncountable.

Number of statements that are correct is ______.

Question 5

Find the solution for the following instance of post correspondence problem
,,,,,

Question 6

Consider the following grammar :

S ABa / aAb / aC

A aB /

B bA /

C a/b

Identify the grammar after eliminating null productions :

Question 7

Consider the following transition table from PDA.

[Example: In above table
Consider the following languages.

How many of the above language are subset of the language L where L is the language accepted y the given PDA?

Question 8

Consider a language L which is described as a deterministic pushdown automaton with empty stack. Which of the following problem is undecidable by Language L?

Question 9

L and are 2 complementary languages , consider the following statements :

(RE : Recursively Enumerable)

(REC : Recursive)

S1 : Both are REC

S2 : Both are RE

S3 : One is REC , other is RE

S4 : Both are RE but not REC

S5 : One is REC and other is not RE

S6 : One is REC , other is RE but not REC.

S7 : One is not RE , other is RE.

How many of the above statements are false ____________.

Question 10

Consider the following statements about L:

1) L is accepted by multi-tape Turing machine, M1

2) L is also accepted by a single tape Turing Machine, M2

Then which of the following is correct?

Question 11

Consider the following problems , which among them can be implemented on a Turing machine :

S1 : Calculating GCD of two numbers

S2 : Copying string

S3 : Predicting the result of tomorrow's cricket match

S4 : Calculating surface area of a given cone dimensions

Question 12

Consider the following statements regarding alphabet and language inequalities.

Which of the above statements are always true?

Question 13

The value of a R.E r over ∑, denoted by val(r), is defined as follows:

1) Val(ϕ) = 0

2) Val( € ) = 0

3) Val ( a ) = 0 ¥ a € ∑

4) Val ((rs)) = val ((r + s )) = max. (val(r), val(s))

5) Val (()) = val (r) + 1

Find the value of the following R.E-

Question 14

Consider the following PDA:

Identify the language accepted by the PDA:

Question 15

Consider the following languages over the alphabet Σ = {0, 1, c}

L1 = {0n1n | n ≥ 0}

L2 = {wcwr | wϵ{0, 1} * }

L3 = {wwr | wϵ {0, 1}*}

Here wr is the reverse of the string w. Which of these languages are deterministic Context free languages?

• 615 attempts