GATE CS Theory of Computation : National Champion Test for GATE & PSU CS Exams

Question 1

Aliasing in the context of programming languages refers to

Question 2

The language accepted by a Pushdown Automaton in which the stack is limited to10 items is best described as

Question 3

Language accepted by the following PDA is ___

Note: e is epsilon and c is special symbol.

Question 4

Consider the following two statements:
S1: {0²ⁿ|n≥ 1} is a regular language
S2: {0^m1ⁿ0^m+n|m ≥ 1 and n ≥ 1} is a regular language
Which of the following statements is correct?

Question 5

Which of the following is TRUE?

Question 6

The lexical analysis for a modem computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

Question 7

Which of the following is true for the language {a^p | p is a prime}?

Question 8

If L and

are recursively enumerable then L is

Question 9

Nobody knows yet if P = NP. Consider the language L defined as follows.

Which of the following statements is true?

Question 10

The problem 3-SAT and 2-SAT are

Question 11

Let S and T be language over Σ={a,b} represented by the regular expressions(a+b*)* and (a+b)*, respectively. Which of the following is true?

Question 12

Consider the following PDA.

Identify the language accepted by the above PDA?

Question 13

Consider the following CFG.

How many derivative steps required to derive the string "abegff" using the above grammar when start symbol 'S' is available?

Question 14

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 15

Which of the following is a regular language?

Question 16

Which of the following is non-regular language?

Question 17

Deterministic CFLs are not closed under _____

Question 18

Consider the languages
L₁ = {ww^R |w

{0, 1}*}
L₂ = {w # w^R | w

{0, 1}*}, where # is a special symbol
L₃ = {ww| w

(0, 1}*)
Which one of the following is TRUE?

Question 19

Let L₁ be a recursive language, and let L₂ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

Question 20

Consider the following deterministic finite state automaton M.

Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is

Question 21

Let G = ({S},{a,b},R,S) be a context free grammar where the rule set R is S → a S b | S S | ε
Which of the following statements is true?

Question 22

The smallest finite automaton which accepts the language {x| length of x is divisible by 3} has

Question 23

Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

Question 24

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

Question 25

Which one of the following is TRUE?

Question 26

Given below are two finite slate automata (→indicates the start state and F indicates a final state)
Y:

Z:

Which of the following represents the product automaton Z x Y?

Question 27

The finite state machine described by the following state diagram with a as starting state, where an arc label is

and x stands for 1-bit input and y stands for 2-bit output

Question 28

The following diagram represents a finite state machine which takes as input a binary number from the least significant bit.

Which one of the following is TRUE?

Question 29

Let L be any regualr language. If L* is regular language then what is L?

Question 30

Assume and are three regular expressions.
Given, for any and
Which of the following could be correct condition which always satisfies the above equation.
(i)
(ii)
(iii)