GATE CSE concept:context-free-languages PYQs & Answers

Home
GATE
Computer Science and Information Technology
Topics
concept:context-free-languages

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–9 of 9. Imported answers require independent review unless marked reviewed.

Topic practice 9 questionsPage 1 of 1

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

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

, 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

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

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

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

Let

be a regular language and

be a context-free language. Which of the following languages is/are context-free?

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 L₁, L₂ be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?

I. L₁ ∪ L₂ is context-free. II. L̅₁ is context-free. III. L₁ − R is context-free. IV. L₁ ∩ L₂ is context-free.

Your answerChoose one option.

I, II and IV only

I and III only

II and IV only

I 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 over the alphabet

. Let

and

Which of the following are context-free languages?

II.

Your answerChoose one option.

I only

II only

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

GATE CSE concept:context-free-languages PYQs

How to practice concept:context-free-languages

Question 24

Question 30

Question 45

Question 24

Question 23

Question 1

Question 12

Question 4

Question 38