GATE CSE Theory of Computation PYQs & Answers — Page 6

Home
GATE
Computer Science and Information Technology
Topics
Theory of Computation

Questions 51–60 of 83. Imported answers require independent review unless marked reviewed.

Topic practice 83 questionsPage 6 of 9

In a pushdown automaton

, a transition of the form

Diagram for Computer Science and Information Technology question 51

where

, and

, represents

Consider the following pushdown automaton over the input alphabet

and stack alphabet

Diagram for Computer Science and Information Technology question 51 (figure 2)

The number of strings of length 100 accepted by the above pushdown automaton is __________.

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 represents the set of all binary strings with an odd number of 1’s?

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

Consider the following statements.

I. If

is regular, then both

and

must be regular.

II. The class of regular languages is closed under infinite union.

Which of the above statements is/are TRUE?

Your answerChoose one option.

I only

II only

Both I and II

Neither I nor II

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

Consider the language

and the following statements.

is deterministic context-free.

II.

is context-free but not deterministic context-free.

III.

is not LL(k) for any

Which of the above statements is/are TRUE?

Your answerChoose one option.

I only

II only

I and II only

III only

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.

The number of reduction steps taken by a bottom-up parser while accepting the string

is ________.

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 languages are undecidable? Note that

indicates encoding of the Turing machine

on input

reaches state

in exactly 100 steps

is not recursive

contains at least 21 members

Your answerChoose one option.

and

only

and

only

and

only

and

only

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

Consider the following languages.

. Which one of the following is TRUE?

Your answerChoose one option.

is regular and

is context-free.

is context-free but not regular and

is context-free.

Neither

nor

is context-free.

is context-free but

is not 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 language.

The minimum number of states in a DFA that accepts

is ______.

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

is a regular language over

, which one of the following languages is NOT regular?

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

For

, let us consider the regular language

. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for

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 51

Question 7

Question 8

Question 10

Question 24

Question 26

Question 32

Question 51

Question 7

Question 15