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

Questions 31–40 of 83. Imported answers require independent review unless marked reviewed.

Which of the following statements is/are CORRECT?

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

The intersection of two regular languages is regular.

The intersection of two context-free languages is context-free.

The intersection of two recursive languages is recursive.

The intersection of two recursively enumerable languages is recursively enumerable.

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

Consider the context-free grammar

below

where

and

are non-terminals, and

and

are terminal symbols. The starting non-terminal is

Which one of the following statements is CORRECT?

Your answerChoose one option.

The language generated by

is not 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 pushdown automaton (PDA)

below, which runs on the input alphabet

, has stack alphabet

, and has three states

, with

being the start state. A transition from state

to state

, labelled

, where

is an input symbol or

is a stack symbol, and

is a string of stack symbols, represents the fact that in state

, the PDA can read

from the input, with

on the top of its stack, pop

from the stack, push in the string

on the stack, and go to state

. In the initial configuration, the stack has only the symbol

in it. The PDA accepts by empty stack.

Which one of the following options correctly describes the language accepted by

Diagram for Computer Science and Information Technology question 40

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 language

over the alphabet

, given below:

The minimum number of states in a Deterministic Finite-State Automaton (DFA) for

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 correctly represents the language of the finite automaton given below?

Diagram for Computer Science and Information Technology question 12

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 of the following statements is/are TRUE?

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

Every subset of a recursively enumerable language is recursive.

If a language

and its complement

are both recursively enumerable, then

must be recursive.

Complement of a context-free language must be recursive.

and

are regular, then

is deterministic context-free.

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 is/are undecidable?

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

Given two Turing machines

and

, decide if

Given a Turing machine

, decide if

is regular.

Given a Turing machine

, decide if

accepts all strings.

Given a Turing machine

, decide if

takes more than

steps on 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 languages:

Note that

is the reversal of the string

. Which of the following is/are TRUE?

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

and

are regular.

and

are context-free.

is regular and

is context-free.

and

are context-free but not regular.

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 of the following statements is/are FALSE?

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

is not context-free but

and

are deterministic context-free.

Neither

nor

is context-free.

and

all are context-free.

Neither

nor its complement is context-free.

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

Suppose that

is a regular language and

is a context-free language. Which one of the following languages is NOT necessarily 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

GATE CSE topic:theory-computation PYQs

Question 24

Question 39

Question 40

Question 63

Question 12

Question 23

Question 46

Question 47

Question 48

Question 1