Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged tbb-toc-1
6
votes
2
answers
1
Test by Bikram | Theory of Computation | Test 1 | Question: 30
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is: Decidable Undecidable but semi-decidable Not even semi-decidable Indeterminable
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
601
views
tbb-toc-1
0
votes
1
answer
2
Test by Bikram | Theory of Computation | Test 1 | Question: 29
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an: Decidable problem Undecidable problem Cannot ascertain None
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
168
views
tbb-toc-1
0
votes
1
answer
3
Test by Bikram | Theory of Computation | Test 1 | Question: 28
Recursive Enumerable Languages are NOT closed under : Union Intersection Complement Homomorphism
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
79
views
tbb-toc-1
0
votes
1
answer
4
Test by Bikram | Theory of Computation | Test 1 | Question: 27
If $S$ and $T$ are languages over $\Sigma =\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$ respectively, then which of the following options is CORRECT? $S \subset T$ $T \subset S$ $S = T$ $S \cap T = \emptyset$
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
84
views
tbb-toc-1
regular-expression
easy
1
vote
1
answer
5
Test by Bikram | Theory of Computation | Test 1 | Question: 26
$L1$ and $L2$ are regular languages. $L3$ is CFL and $L4$ is a recursive enumerable language. $L5$ is the reversal of $L4$. If $L6= \{ (L3/y)$ intersection $L5 \}$ where $y$ is input alphabet, then $L6$ is a: Regular Language CFL Recursive Enumerable Language Non Recursive Enumerable Language
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
396
views
tbb-toc-1
4
votes
1
answer
6
Test by Bikram | Theory of Computation | Test 1 | Question: 25
If all the strings of a language can be enumerated in $\text{lexicographic}$ order, then this is an example of a _______ language. Regular CFL but need not be regular CSL but need not be a CFL Recursive but need not be a CSL
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
387
views
tbb-toc-1
0
votes
0
answers
7
Test by Bikram | Theory of Computation | Test 1 | Question: 24
By reading any string, which of the following is possible for a Turing Machine? TM halts in Final State TM halts in Non Final State TM enters into Infinite Loop All of these
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
75
views
tbb-toc-1
1
vote
2
answers
8
Test by Bikram | Theory of Computation | Test 1 | Question: 23
PDA can be used for: infix to postfix conversion implementing recursive function calls evaluating arithmetic expressions all of the above
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
137
views
tbb-toc-1
3
votes
2
answers
9
Test by Bikram | Theory of Computation | Test 1 | Question: 22
Total Recursive Functions are similar to: Recursive Languages Recursive Enumerable Languages Cannot relate the two None
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
355
views
tbb-toc-1
4
votes
2
answers
10
Test by Bikram | Theory of Computation | Test 1 | Question: 21
Consider the following grammar: $G$ $E \rightarrow E+E \mid E-E \mid E^*E \mid (E)\mid \text{id}$ The number of derivation trees for the string $\text{id} +\text{id} ^* \text{id} – \text{id}$ is: $5$ $6$ $7$ $8$
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
344
views
tbb-toc-1
2
votes
1
answer
11
Test by Bikram | Theory of Computation | Test 1 | Question: 20
Which of the following is not a Regular Expression? $[(a+b)^* – (aa+bb)]^*$ $[(0+1) – (0b + a1)^* (a+b)]^*$ $(01+11+10)^*$ $(1+2+0)^* (1+2)^*$
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
350
views
tbb-toc-1
3
votes
1
answer
12
Test by Bikram | Theory of Computation | Test 1 | Question: 19
Consider the following CFG : $S \rightarrow AB$ $A \rightarrow BC \mid a$ $B \rightarrow CC \mid b$ $C \rightarrow a \mid AB$ The Rank of Variable $A$ is: $2$ $3$ $4$ not possible to define
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
525
views
tbb-toc-1
1
vote
1
answer
13
Test by Bikram | Theory of Computation | Test 1 | Question: 18
The regular set $A =(01+1)^*$ and the regular set $B =((01)^*1^*)^*$ Which of the following statements is TRUE? $A$ is a subset of $B$ $B$ is a subset of $A$ $A$ and $B$ are incomparable $A=B$
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
113
views
tbb-toc-1
2
votes
2
answers
14
Test by Bikram | Theory of Computation | Test 1 | Question: 17
The language $L =\{a^n \ b^n \mid n \geq 1\} \cup \{a^m \ b^{2m} \mid m \geq 1\}$ is: DCFL CFL but not DCFL Non-CFL Regular Language
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
227
views
tbb-toc-1
identify-class-language
2
votes
1
answer
15
Test by Bikram | Theory of Computation | Test 1 | Question: 16
The Minimal Finite Automata accepting the set of all strings over $(0+1)^*$ that do NOT have the sub-string $0001$ has: $5$ states $6$ states $7$ states $9$ states
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
217
views
tbb-toc-1
0
votes
3
answers
16
Test by Bikram | Theory of Computation | Test 1 | Question: 15
Which one is a correct statement in terms of accepting powers of DPDA and NPDA? DPDA and NPDA are equal DPDA and NPDA are not comparable DPDA < NPDA DPDA > NPDA
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
93
views
tbb-toc-1
0
votes
2
answers
17
Test by Bikram | Theory of Computation | Test 1 | Question: 14
Consider the grammar given below : $S \rightarrow AB \mid DA$ $B \rightarrow BCD \mid ABD \mid CC \mid b$ $A \rightarrow a \mid BC$ $C \rightarrow aBD \mid a$ $C \rightarrow aBCAD \mid DaB$ $A \rightarrow aBCAD \mid Da$ ... following non terminal is useless in the grammar (as non terminal strings can be derived from it): $D$ $C$ $B$ $A$
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
202
views
tbb-toc-1
grammar
6
votes
1
answer
18
Test by Bikram | Theory of Computation | Test 1 | Question: 13
An NFA has $10$ states out of which $3$ are final states. The maximum number of final states in converted DFA is: $895$ $894$ $896$ $897$
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
567
views
tbb-toc-1
0
votes
1
answer
19
Test by Bikram | Theory of Computation | Test 1 | Question: 12
Let $N(f) =$ the class of languages accepted by Non- deterministic Finite Automata, $N(p) =$ the class of languages accepted by Non- deterministic Push down Automata, $D(f)=$ the class of languages accepted by Deterministic Finite Automata; and, $D(p)=$ the class of ... $D(p) = N(p)$ $D(f) = N(f)$ and $D(p)$ subset of $N(p)$
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
97
views
tbb-toc-1
2
votes
2
answers
20
Test by Bikram | Theory of Computation | Test 1 | Question: 11
Identify the Regular Expression among the following which denotes ALL strings of $a$'s and $b$'s, where each string contains at least $2$ $b$'s: $(a+b)^*ba^*b$ $(a+b)^*ba^*ba$ $(a+b)^*ba^*b(a+b)^*$ $(a+b)^*ab^*ab$
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
186
views
tbb-toc-1
1
vote
1
answer
21
Test by Bikram | Theory of Computation | Test 1 | Question: 10
Consider the language $L =\{ ab^2 wb^3 / w$ is an element of $(a+b)^* \}$. $L$, therefore, is: regular CFL but not regular CSL but not CFL none
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
152
views
tbb-toc-1
1
vote
1
answer
22
Test by Bikram | Theory of Computation | Test 1 | Question: 9
Regular Languages are not closed under ______ operator. Union Concatenation Subset Division
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
198
views
tbb-toc-1
2
votes
1
answer
23
Test by Bikram | Theory of Computation | Test 1 | Question: 8
Which of the following sets can be recognized by a Deterministic Finite State Automation? The numbers $2^0, \ 2^1$ to $2^n$ written in unary. The numbers $2^0, \ 2^1$ to $2^n$ written in binary. The set of binary strings where the number of zeros is the same as the number of ones. The set $\{1,101,11011,1110111, \dots \}$
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
290
views
tbb-toc-1
regular-language
1
vote
1
answer
24
Test by Bikram | Theory of Computation | Test 1 | Question: 7
How many states are there in the minimal DFA that accept the following language? $L= \{x \mid x$ is a binary string with number of $0$'s divisible by $2$ and number of $1$'s divisible by $3 \}$ $6$ $5$ $3$ $2$
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
160
views
tbb-toc-1
4
votes
1
answer
25
Test by Bikram | Theory of Computation | Test 1 | Question: 6
If L is any regular language accepted by Minimal Finite Automaton with $n$ states, then the number of states in Minimal Finite Automaton to accept Prefix(L) is: $n$ $n+1$ $n+2$ $2n$
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
491
views
tbb-toc-1
minimal-state-automata
3
votes
0
answers
26
Test by Bikram | Theory of Computation | Test 1 | Question: 5
If a language L1 is polynomially reduced to the language L2 and L2 is polynomially reduced to the language L1, then which of the following cannot be TRUE? L1 is decidable and L2 is undecidable. L1 is regular and L2 is CFL. L1 is recursive and L2 is recursively enumerable. L1 is decidable and L2 is decidable.
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
446
views
tbb-toc-1
1
vote
1
answer
27
Test by Bikram | Theory of Computation | Test 1 | Question: 4
If $r1$ ,$r2$ and $r3$ are the accepting powers of DFA, NFA and NFA with Epsilon - moves, then ____________. $r1=r2=r3$ $r1 < r2 = r3$ $r1 = r2 < r3$ $r1$ not equal to $r2$ not equal to $r3$
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
103
views
tbb-toc-1
3
votes
1
answer
28
Test by Bikram | Theory of Computation | Test 1 | Question: 3
Which of the following grammars violate the Chomsky Normal Form? $S \rightarrow AB$, $A \rightarrow a , B \rightarrow \epsilon \mid b$ $S \rightarrow AcB, A \rightarrow a, B \rightarrow b$ $S \rightarrow AB, \ A \rightarrow a, \ B \rightarrow b$ All of the above (i) only (i) and (ii) only (ii) and (iii) only
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
226
views
tbb-toc-1
1
vote
1
answer
29
Test by Bikram | Theory of Computation | Test 1 | Question: 2
The minimal DFA that accepts all strings of a's and b's, and ends with 'aa' has _____ number of states.
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
235
views
tbb-toc-1
numerical-answers
1
vote
1
answer
30
Test by Bikram | Theory of Computation | Test 1 | Question: 1
Let $L$ denote the language generated by the grammar $S \rightarrow 00T$, $T \rightarrow 11S \mid 11$. If $S$ is the start symbol, then which among the following options is TRUE? $L = (0+1)^*$ $L$ is regular but not $(0+1)^*$ $L$ is context free but not regular $L$ is not context free
Bikram
asked
in
Theory of Computation
Nov 26, 2016
by
Bikram
221
views
tbb-toc-1
identify-class-language
To see more, click for the
full list of questions
or
popular tags
.
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
-tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
BITSHD 2023
My journey from being a MSc student to AIR 239 in GATE CSE 2023 and qualified UGC-NET JRF.
NEEPCO Recruitment 2023
GATE CSE 2023 Results
IIIT Banglore MTech 2023-24
Subjects
All categories
General Aptitude
(2.5k)
Engineering Mathematics
(9.3k)
Digital Logic
(3.3k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.7k)
Non GATE
(1.3k)
Others
(2.5k)
Admissions
(653)
Exam Queries
(845)
Tier 1 Placement Questions
(17)
Job Queries
(76)
Projects
(9)
Unknown Category
(866)
Recent questions tagged tbb-toc-1
Recent Blog Comments
Please provide some tips about NET, since I want...
Amazing story to hear
Link added now:...
Sir can you please provide some good resources...
Where can we see the responses of the form filled?