GATE CSE Theory of Computation PYQs & Answers

Home
GATE
Computer Science and Information Technology
Topics
Theory of Computation

Attempt a question, record the concept and assumptions, then check the available answer. Rework mistakes after revising the relevant concepts. Topic tags can overlap; review the question context.

Questions 1–10 of 83. Imported answers require independent review unless marked reviewed.

Topic practice 83 questionsPage 1 of 9

Which one of the following statements is equivalent to the following assertion?

Turing machine

decides the language

Your answerChoose one option.

Turing machine

halts on all input strings in

Turing machine

accepts all input strings in

Turing machine

rejects all input strings in

Turing machine

accepts all input strings in

and rejects all input strings in

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

Consider the following grammar where

is the start symbol, and

and

are terminal symbols.

Which of the following statements is/are true?

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

The grammar is ambiguous

The string

has two distinct derivations in this grammar

The string

has only one rightmost derivation

The language generated by the grammar is undecidable

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

Let

be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet.

Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to

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

128

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

Which of the following grammars is/are ambiguous?

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

Consider the following two finite automata

and

Diagram for Computer Science and Information Technology question 47

Which of the following statements is/are true?

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

is a proper subset of

consists of all strings in

whose length is divisible by 3

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

Let

and let

Which of the following constraints ensure(s) that the language

is context-free?

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

and

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

Let

and

be two languages over a finite alphabet, such that

and

are regular languages. Which of the following statements is/are always true?

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

is regular

is context-free

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

Consider the following context-free grammar

In the above grammar,

is the start symbol,

and

are terminal symbols, and

and

are non-terminal symbols.

Let

be the language generated by the grammar

. For a string

, let

be the number of

’s in

and

be the number of

’s in

Which of the following statements is/are true?

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

There is a string

such that

For every string

There is a string

such that

For every string

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

Consider the following context-free grammar

, where

, and

are the variables (non-terminals),

and

are the terminal symbols,

is the start variable, and the rules of

are described as:

Which ONE of the languages

is accepted by

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

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

Your answerChoose one option.

Any regular language.

Any context-free language.

Any language accepted by a non-deterministic pushdown automaton.

Any decidable language.

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

How to practice Theory of Computation

Question 13

Question 25

Question 26

Question 29

Question 47

Question 48

Question 51

Question 52

Question 19

Question 24