Computer Science and Information Technology
GATE CSE Theory of Computation PYQs
Build your understanding with focused practice from past exam papers.
Questions 21–30 of 83. Imported answers require independent review unless marked reviewed.
Question 23
Open questionCS1MSQ1 markNeeds review
Let
be two regular languages and
a language which is not regular. Which of the following statements is/are always TRUE?Your answerSelect all correct options. You can choose more than one.
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 questionCS1MCQ2 marksNeeds review
Consider the following grammar
, with
as the start symbol. The grammar
has three incomplete productions denoted by (1), (2), and (3).
The set of terminals is
. The FIRST and FOLLOW sets of the different non-terminals are as follows.
Which one of the following options CORRECTLY fills in the incomplete productions?
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 41
Open questionCSMCQ2 marksNeeds review
Let M be the 5-state NFA with ε-transitions shown in the diagram below.
Which one of the following regular expressions represents the language accepted by M?
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 50
Open questionCS1MSQ2 marksNeeds review
Consider the 5-state DFA
accepting the language
shown below. For any string
let
be the number of 0's in
and
be the number of 1's in
.
Which of the following statements is/are FALSE?
Your answerSelect all correct options. You can choose more than one.
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 52
Open questionCSMSQ2 marksNeeds review
Consider a context-free grammar G with the following 3 rules.
S → aS, S → aSbS, S → c
Let w ∈ L(G). Let n_a(w), n_b(w), n_c(w) denote the number of times a, b, c occur in w, respectively. Which of the following statements is/are TRUE?
Your answerSelect all correct options. You can choose more than one.
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 59
Open questionCS1NAT2 marksNeeds review
Let
be a context-free grammar in Chomsky Normal Form with
and
containing 10 variable symbols including the start symbol
. The string
is derivable from
. The number of steps (application of rules) in the derivation
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 61
Open questionCS1NAT2 marksNeeds review
Consider the following two regular expressions over the alphabet :
The total number of strings of length less than or equal to 5, which are neither in
nor in
, 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 62
Open questionCSNAT2 marksNeeds review
Let
be the language represented by the regular expression
and
, where
denotes the length of string
. The number of strings in
which are also in
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 14
Open questionCSMCQ1 markNeeds review
Consider the Deterministic Finite-state Automaton (DFA) shown below. The DFA runs on the alphabet
, and has the set of states
, with
being the start state and
being the only final state. 
Which one of the following regular expressions correctly describes the language accepted 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 19
Open questionCSMCQ1 markNeeds review
Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions:
letter
[A–Za–z]
digit
[0–9]
id
letter (letter
digit)
Which one of the following Non-deterministic Finite-state Automata with
-transitions accepts the set of valid identifiers? (A double-circle denotes a final state)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