GATE CSE Theory of Computation PYQs & Answers — Page 2

Home
GATE
Computer Science and Information Technology
Topics
Theory of Computation

Questions 11–20 of 83. Imported answers require independent review unless marked reviewed.

Topic practice 83 questionsPage 2 of 9

Let

be Context Free Grammars (CFGs) and

be a regular expression. For a grammar

, let

denote the language generated by

Which ONE among the following questions is decidable?

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

A regular language

is accepted by a non-deterministic finite automaton (NFA) with

states. Which of the following statement(s) is/are FALSE?

Your answerSelect all correct options. You can choose more than one.

may have an accepting NFA with

states.

may have an accepting DFA with

states.

There exists a DFA with

states that accepts

Every DFA that accepts

has

states.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the two lists List I and List II given below:

List I	List II
(i) Context free languages	(a) Closed under union
(ii) Recursive languages	(b) Not closed under complementation
(iii) Regular languages	(c) Closed under intersection

For matching of items in List I with those in List II, which of the following option(s) is/are CORRECT?

Your answerSelect all correct options. You can choose more than one.

(i) – (a), (ii) – (b), and (iii) – (c)

(i) – (b), (ii) – (a), and (iii) – (c)

(i) – (b), (ii) – (c), and (iii) – (a)

(i) – (a), (ii) – (c), and (iii) – (b)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following two languages over the alphabet

Which ONE of the following statements is CORRECT?

Your answerChoose one option.

Both

and

are regular languages.

is a regular language but

is not a regular language.

is not a regular language but

is a regular language.

Neither

nor

is a regular language.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following two languages over the alphabet

, where

and

are natural numbers.

Which ONE of the following statements is CORRECT?

Your answerChoose one option.

Both

and

are context-free languages.

is a context-free language but

is not a context-free language.

is not a context-free language but

is a context-free language.

Neither

nor

are context-free languages.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following deterministic finite automaton (DFA) defined over the alphabet,

. Identify which of the following language(s) is/are accepted by the given DFA.

Diagram for Computer Science and Information Technology question 50

Your answerSelect all correct options. You can choose more than one.

The set of all strings containing an even number of

’s.

The set of all strings containing the pattern

The set of all strings ending with the pattern

The set of all strings not containing the pattern

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider two grammars

and

with the production rules given below:

where

are the terminals.

Which of the following option(s) is/are CORRECT?

Your answerSelect all correct options. You can choose more than one.

is not

and

is not

and

are not

and

are ambiguous.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let

. For

, and

, let

denote the number of occurrences of

Which one or more of the following option(s) define(s) regular language(s)?

Your answerSelect all correct options. You can choose more than one.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let

. For

, let

be the product of symbols in

modulo 7. We take

, where

is the null string.

For example,

Define

The number of states in a minimum state DFA for

is __________. (Answer in integer)

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?

Diagram for Computer Science and Information Technology question 22

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

GATE CSE Theory of Computation PYQs

Question 25

Question 28

Question 30

Question 44

Question 45

Question 50

Question 51

Question 52

Question 60

Question 22