GATE CSE topic:theory-computation PYQs & Answers — Page 7

Questions 61–70 of 83. Imported answers require independent review unless marked reviewed.

Which one of the following languages over

is NOT context-free?

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 sets: S1. Set of all recursively enumerable languages over the alphabet

S2. Set of all syntactically valid C programs S3. Set of all languages over the alphabet

S4. Set of all non-regular languages over the alphabet

Which of the above sets are uncountable?

Your answerChoose one option.

S1 and S2

S3 and S4

S2 and S3

S1 and S4

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

Let Σ be the set of all bijections from {1, ..., 5} to {1, ..., 5}, where id denotes the identity function, i.e. id(i) = i, ∀i. Let ∘ denote composition on functions. For a string x = x₁ x₂ ··· xₙ ∈ Σⁿ, n ≥ 0, let π(x) = x₁ ∘ x₂ ∘ ··· ∘ xₙ. Consider the language L = {x ∈ Σ* | π(x) = id}. The minimum number of states in any DFA accepting L is ________.

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

In an RSA cryptosystem, the value of the public modulus parameter n is 307. If it is also known that φ(n) = 288, where φ() denotes Euler’s Totient Function, then the prime factor of n which is greater than 50 is ________.

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

Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

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

The set of all recursively enumerable languages is

Your answerChoose one option.

closed under complementation.

closed under intersection.

a subset of the set of all recursive languages.

an uncountable set.

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

Consider the first-order logic sentence

where

is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose

has a model with a universe containing 7 elements. Which one of the following statements is necessarily true?

Your answerChoose one option.

There exists at least one model of

with universe of size less than or equal to 3.

There exists no model of

with universe of size less than or equal to 3.

There exists no model of

with universe of size greater than 7.

Every model of

has a universe of size equal to 7.

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:

II.

III.

IV.

Which of the languages above are context-free?

Your answerChoose one option.

I and IV only

I and II only

II and III only

II and IV 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 problems.

denotes the language generated by a grammar

denotes the language accepted by a machine

(I) For an unrestricted grammar

and a string

, whether

(II) Given a Turing machine

, whether

is regular (III) Given two grammars

and

, whether

(IV) Given an NFA

, whether there is a deterministic PDA

such that

and

accept the same language.

Which one of the following statements is correct?

Your answerChoose one option.

Only I and II are undecidable

Only III is undecidable

Only II and IV are undecidable

Only I, II and III are undecidable

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

Given a language

, define

as follows:

for all

Diagram for Computer Science and Information Technology question 52

The order of a language

is defined as the smallest k such that

. Consider the language

(over alphabet 0) accepted by the following automaton.

The order of

is _____.

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

GATE CSE topic:theory-computation PYQs

Question 31

Question 34

Question 48

Question 54

Question 6

Question 7

Question 28

Question 35

Question 36

Question 52