Computer Science and Information Technology
GATE CSE topic:theory-computation PYQs
Build your understanding with focused practice from past exam papers.
Questions 71–80 of 83. Imported answers require independent review unless marked reviewed.
Question 4
Open questionCSMCQ1 markNeeds review
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.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 10
Open questionCSMCQ1 markNeeds review
Consider the following context-free grammar over the alphabet
with
as the start symbol:
Which one of the following represents the language generated by the above grammar?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 16
Open questionCSMCQ1 markNeeds review
Identify the language generated by the following grammar, where S is the start variable.
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 22
Open questionCSNAT1 markNeeds review
Consider the language
given by the regular expression
over the alphabet
. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting
is ____________.Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 25
Open questionCSNAT1 markNeeds review
The minimum possible number of states of a deterministic finite automaton that accepts the regular language
is __________.Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 32
Open questionCSMCQ2 marksNeeds review
Consider the following expression grammar
:E
E − T | TT
T + F | FF
(E) | idWhich of the following grammars is not left recursive, but is equivalent to
?Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 34
Open questionCSMCQ2 marksNeeds review
If
is a grammar with productions
where
is the start variable, then which one of the following strings is not generated by
?Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 37
Open questionCSMCQ2 marksNeeds review
Consider the context-free grammars over the alphabet
given below.
and
are non-terminals.
The language
isYour answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 38
Open questionCSMCQ2 marksNeeds review
Consider the following languages over the alphabet
. Let
and
.Which of the following are context-free languages?
I.
II.
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 39
Open questionCSMCQ2 marksNeeds review
Let
and
be finite alphabets and let
be a symbol outside both
and
. Let
be a total function from
to
. We say
is computable if there exists a Turing machine
which given an input
in
, always halts with
on its tape. Let
denote the language
. Which of the following statements is true:Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer