ISRO Exam CS 2017: National Champion test :Theory of Computation for GATE & PSU CS Exams

Question 1

If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

Question 2

Match the following:

Question 3

Which of the following pairs have DIFFERENT expressive power?

Question 4

Definition of a language L with alphabet {a} is given as following.
L= {a^nk | k>0, n is positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?

Question 5

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Question 6

Which of the following is CFL but not DCFL

Question 7

Consider the languages L1, L2 and L3 as given below.
L1 = {0^p 1^q | p,q ∈ N},
L2 = {0^p 1^q | p,q ∈ N, and p=q} and
L3 = {0^p 1^q 0^r| p,q,r ∈ N, and p=q=r}

Which of the following statements is NOT TRUE?

Question 8

Which of the following statement is correct?

Question 9

If L and

are recursively enumerable then L is

Question 10

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

Question 11

Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a context-free language, then, is L’ also context-free?
3) If L is a regular language, then, is L’ also regular?
4) If L is a recursive language, then, is L’ also recursive?

Question 12

What is the complement of the language accepted by the NFA shown below?
Assume Σ = {a} and ε is the empty string.

Question 13

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?

Question 14

Let L = {(a^p)^* | p is a prime number} and How many minimum number of states in NFA that accepts a language L?

Question 15

Let N_f and N_p denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let D_f and D_p denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?

Question 16

Which of the following are regular sets?
I. {aⁿb^2m | n ≥ 0, m ≥ 0}
II. {aⁿb^m | n = 2m}
III. {aⁿb^m | n ≠ m}
IV. {xcy | x,y ∈{a,b}*}

Question 17

The language generated by the following grammar over the alphabet {a, b} can be described as the set of ____
S → aSa | bSb | a | b

Question 18

Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

Question 19

Which of the following problem is not decidable

Question 20

Find the grammar that generates an inherently ambiguous context free language.